هندسه‌ی محاسباتی
اهداف درس
هدف از این درس، آشنایی دانش‌جویان با داده‌ساختارها و الگوریتم‌های کارا برای حل مسائل هندسی است. موضوعات ارائه‌شده در این درس در سایر حوزه‌های علوم کامپیوتر از جمله گرافیک کامپیوتری، روباتیک، سیستم‌های اطلاعات جغرافیایی و پایگاه‌های داده مورد استفاده قرار می‌گیرند.
ریز مواد
- مقدمه
- معرفی درس، نمونه مسائل هندسی
- پوسته‌ی محدب
- محاسبه‌ی پوسته‌ی محدب در صفحه، عملیات پایه‌ی هندسی
- چند روش برای محاسبه‌ی پوسته‌ی محدب در صفحه
- اثبات کران پایین، قضیه‌ی بن-اُر
- الگوریتم‌های حساس به خروجی، دو الگوریتم بهینه از چن
- دوگان هندسی
- دوگان نقاط، پوش‌های بالایی و پایینی، کاربردها، دوگان در فضای سه‌بعدی
- پوسته‌ی محدب در فضای سه‌بعدی
- پیچیدگی ترکیبیاتی، نحوه‌ی نمایش، الگوریتم کادوپیچی
- الگوریتم تصادفی کلارکسون-شور، پوسته‌ی محدب در فضاهای بالاتر
- تقاطع و چینش خطوط
- ساخت چینش خطوط، الگوریتم افزایشی، قضیه‌ی قلمرو یک خط
- تقاطع پاره‌خط‌ها، الگوریتم جاروب صفحه، الگوریتم تقسیم و حل
- نمودار ورونوی و مثلث‌بندی دلونی
- تعریف نمودار ورونوی، ویژگی‌ها و قضایا
- مثلث‌بندی دلونی و خواص آن، الگوریتم فورچیون
- ارتباط با پوسته‌ی محدب، الگوریتم تصادفی ساخت
- کاربردهای نمودار ورونوی و مثلث‌بندی دلونی، نمودار ورونوی مرتبه‌ی بالاتر
- برنامه‌ریزی خطی
- تعریف برنامه‌ریزی خطی، کاربردهای هندسی در فضای پایین
- الگوریتم هرس و جست‌وجوی مگیدو، الگوریتم تصادفی-افزایشی سایدل
- الگوریتم نمونه‌برداری تصادفی کلارکسون
- مسائل شبیه به برنامه‌ریزی خطی، کوچک‌ترین دایره‌ی محیطی
- مکان‌یابی نقاط
- روش تقسیم و حل، نقشه‌ی ذوزنقه‌ای، الگوریتم افزایشی تصادفی
- الگوریتم هرس و جست‌وجوی کرکپاتریک
- مثلث‌بندی چندضلعی
- روش ذوزنقه‌بندی، الگوریتم تصادفی سایدل
- کاربردهای مثلث‌بندی، مسئله‌ی گالری هنر
- جست‌وجوی بازه‌ای
- بازه‌های متعامد: درخت کی‌دی، درخت بازه، آبشار کسری
- بازه‌های کلی، درخت افراز، درخت برش
- پنجره‌بندی، درخت جست‌وجوی اولویت، درخت پاره‌خط
ارزیابی
- آزمون‌های میان‌ترم و پایان‌ترم (۱۰ نمره)
- سه تمرین نظری (۶ نمره)
- پروژه‌ی پژوهشی (۴ نمره)
مراجع
- M. de Berg, O. Cheong, M. van Kreveld, and M. Overmars. Computational Geometry: Algorithms and Applications. Third edition, Springer-Verlag, 2008.
- J. O'Rourke. Computational Geometry in C. Second edition, Cambridge University Press, 1998.