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

Advanced Computational Geometry

مقطع: تحصیلات تکمیلی گرایش: الگوریتم‌ها و محاسبات
نوع درس: نظری تعداد واحد: ۳
پیش‌نیاز: – هم‌نیاز: –

هدف کلی

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

سرفصل‌ها

  1. تقریب هندسی
  2. هندسه در ابعاد بالا
  3. مسائل مجاورت (Proximity Problems)
  4. افراز به زوج‌های ازهم‌جدا (WSPD)
  5. پوشاننده‌های هندسی (Geometric Spanners)
  6. مسائل ان‌پی-سخت هندسی
  7. مسائل هندسی در مدل جریان داده
  8. هندسه‌ی ترکیبیاتی
  9. پوش‌های پایینی (Lower Envelopes)
  10. سطوح و لایه‌ها
  11. ε-نت‌ها، بُعد VC و کاربردها
  12. داده‌ساختارهای پویا و جنبشی

ارزیابی پیشنهادی

منابع پیشنهادی

  • 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. 3rd Edition, CRC Press, 2017.