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

اهداف درس

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

ريز مواد

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

ارزیابی

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

مراجع

  • مقالات مرتبط با موضوعات درس که لینک آن‌ها در وبگاه درس قرار داده خواهد شد.
  • S‎. ‎Har-Peled‎. ‎Geometric Approximation Algorithms. ‎American Mathematical Society‎, ‎2011.‎
  • J‎. ‎Matousek‎. ‎Lectures on Discrete Geometry. ‎Springer-Verlag‎, ‎2002‎.
  • G‎. ‎Narasimhan and M‎. ‎Smid‎. ‎Geometric Spanner Networks. ‎‎Cambridge University Press‎, ‎2007.‎
  • J‎. ‎Goodman and J‎. ‎O'Rourke (eds.).‎ ‎Handbook of Discrete and Computational Geometry. ‎2nd edition‎, ‎CRC Press‎, ‎2004‎.
  • M‎. ‎de Berg‎, ‎O‎. ‎Cheong‎, ‎M‎. ‎van Kreveld‎, ‎and M‎. ‎Overmars‎. ‎Computational Geometry‎: Algorithms and Applications. ‎Third edition‎, ‎Springer-Verlag‎, ‎2008.‎