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

Advanced Computational Geometry

شماره درس: ۴۰۷۹۵.۱ تعداد واحد: ۳
مقطع: کارشناسی ارشد نوع درس: نظری
پیش‌نیاز: هندسه محاسباتی هم‌نیاز: –

اهداف درس

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

ریز مواد

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

ارزیابی

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

مراجع

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