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

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

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

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

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