هندسه محاسباتی پیشرفته

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

• تقریب هندسی
  گرد کردن نقاط و جهت‌ها، مجموعه‌های هسته‌ی هندسی (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، جست‌وجوی عناصر بعدی، الگوریتم‌های دوبخشی

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

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