این درس دربرگیرنده‌ی موضوعاتی از هندسه‌ی محاسباتی است که به زمینه‌های پژوهش روز نزدیک‌ترند و به طور معمول در دروس مقدماتی هندسه‌ی محاسباتی مورد بررسی قرار نمی‌گیرند. مطالب این درس حول سه موضوع کلی متمرکز خواهد بود: الگوریتم‌های تقریبی هندسی، داده‌ساختارهای هندسی، و هندسه‌ی ترکیبیاتی. آشنایی قبلی با هندسه‌ی محاسباتی برای این درس مفید خواهد بود، ولی یک پیش‌نیاز محسوب نمی‌شود.

• ‎تقریب هندسی‎
  گرد کردن نقاط و جهت‌ها، مجموعه‌های هسته‌ی هندسی ‎ (Geometric Coresets) ‎، نمودار ورونوی گسسته
• ‎هندسه در ابعاد بالا‎
  مسائل بهینه‌سازی در بعدهای بالا، برازش اشکال هندسی، مشکل ابعاد زیاد، تکنیک‌های کاهش بعد
• ‎جویبار داده‌ها (‎Data Streams)
  مجموعه‌های هسته‌ی تجزیه‌پذیر، تکنیک ادغام-کاهش، روش مضاعف کردن
• ‎مسائل مجاورت (‎Proximity Problems)
  جست‌وجوی نزدیک‌ترین همسایه، چهاردرخت ‎ (Quadtrees) ‎، چهاردرخت فشرده
• افراز به زوج‌های ازهم‌جدا ‎ (WSPD) ‎
  محاسبه‌ی زوج‌های ازهم‌جدا، کاربرد در ساخت پوشاننده‌ها، تقریب درخت پوشای کمینه‌ی اقلیدسی
• ‎پوشاننده‌های هندسی (Geometric Spanners)
  گراف‌های ‎یائو‎ و تتا، تحلیل ضریب کشش، پوشاننده‌های مبتنی بر لیست پرشی
• مسائل ان‌پی‌سخت هندسی
  فروشنده‌ی دوره‌گرد اقلیدسی، الگوریتم PTAS، مسئله‌ی برچسب‌زنی نقشه‌، مجموعه‌های مستقل هندسی
• هندسه‌ی ترکیبیاتی‎
  مسائل اولیه، مسئله‌ی سیلوستر، مسئله‌ی هاپکرافت، لم تقاطع، مسئله‌ی فاصله‌ی اردوش
• پوش‌های پایینی Lower Envelopes) ‎)
  پوش پایینی خطوط و پاره‌خط‌ها، اندازه‌ی پوش پایینی‎، دنباله‌ی ‎Davenport-Schinzel‎، کاربردها
• سطوح و لایه‌ها
  k‎-مجموعه‌ها و k‎-سطح‌ها، حدود بالای اندازه، اثبات احتمالاتی، عمق توکی (Tukey depth)
• ε‎-نت‌ها
  ε‎-نت‌ها و ε‎-نمونه‌ها، ‎بُعد VC، وجود ‎-ε‎نت‌های کوچک، کاربردها
• ‎داده‌ساختارهای پویا‎
  پوسته‌ی محدب پویا در دو بعد، تکنیک‌های کلی پویاسازی، روش‌های لگاریتمی و رادیکالی
• ‎داده‌ساختارهای جنبشی (‎Kinetic Data Structures)
  درخت تورنمت جنبشی، پوسته‌ی محدب نقاط متحرک، نزدیک‌ترین زوج نقاط متحرک
• ‎مدل ‎Word-RAM (درصورت فرصت)
  درخت‌های ‎van Emde Boas‎ و ‎fusion‎، جست‌وجوی عناصر بعدی، الگوریتم‌های دوبخشی

• آزمون‌های میان‌ترم و پایانی: ۱۰ نمره
• حدود سه تمرین نظری: ۵ نمره
• پروژه‌ی پژوهشی: ۵ نمره

• مقالات مرتبط با موضوعات درس که لینک آن‌ها در وبگاه درس قرار داده خواهد شد.