هندسه‌ی محاسباتی پیشرفته
اهداف درس
این درس دربرگیرنده‌ی موضوعاتی از هندسه‌ی محاسباتی است که به زمینه‌های پژوهش روز نزدیک‌ترند و به طور معمول در دروس مقدماتی هندسه‌ی محاسباتی مورد بررسی قرار نمی‌گیرند. مطالب این درس حول سه موضوع کلی متمرکز خواهد بود: الگوریتم‌های تقریبی هندسی، داده‌ساختارهای هندسی، و هندسه‌ی ترکیبیاتی. آشنایی قبلی با هندسه‌ی محاسباتی برای این درس مفید خواهد بود، ولی یک پیش‌نیاز محسوب نمی‌شود.
ريز مواد
- تقریب هندسی
گرد کردن نقاط و جهت‌ها، مجموعه‌های هسته‌‌ی هندسی (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. 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.