درس هندسه محاسباتی نیمسال 14002

هدف از این درس آشنایی با حوزه هندسه محاسباتی از حوزه‌های جذاب و کاربردی علوم کامپیوتر است. هندسه محاسباتی شامل طراحی، تحلیل و پیاده‌سازی الگوریتم‌ها و داده ساختارهای مربوط به مسائل هندسی است. صرف نظر از جذابیت نظری، این مسائل در حوزه‌های مختلفی شامل گرافیک، روباتیک، سیستم‌های اطلاعات جغرافیایی، ،CAD/CAM پایگاه داده و داده کاوی کاربرد دارند.

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

تمرین ۶ نمره

• در این درس ۴ سری تمرین خواهیم داشت.

تحقیق و کار پژوهشی ۳ نمره

• هر فرد در یک زمینه تحقیق اقدام به مطالعه و تهیه گزارش خواهد کرد و در انتهای نیمسال آن را ارائه خواهد نمود.

میان‌ترم ۵ نمره

پایان‌ترم ۶ نمره

• مباحث مقدماتی: آشنایی با مسائل هندسی و ملاحظات آنها، پوش محدب و دوگان
• تقاطع پاره خط ها: الگوریتم محاسبه تقاطع پاره خط‌ها و داده ساختار نگهداری اشیاء در فضای دوبعدی.
• مثلث‌بندی:الگوریتم مثلث‌بندی و مساله موزه هنر.
• برنامه ریزی خطی: طراحی الگوریتم هندسی برای حل مساله برنامه ریزی خطی و تحلیل تصادفی.
• داده ساختارهای جستجوی هندسی: طراحی داده ساختار هندسی برای جستجوی بازه‌ای، جستجوی محدوده، پاره‌خط و نقطه
• مکان یابی نقاط: الگوریتم و داده ساختار مکان یابی دوبعدی
• نمودار ورونوی و مثلث بندی دلونی: معرفی نمودار ورونوی و مثلث‌بندی دلونی و کاربردهای آن‌ها و الگوریتم های محاسبه آن‌ها.
• داده ساختارهای افراز فضا: داده ساختار افراز دودویی فضا و درخت چهارتایی
• برنامه ریزی حرکت و گراف دید: الگوریتم‌ها و داده ساختارهای طراحی حرکت ربات و قابلیت دید در بخش زیر مرجع اصلی درس آمده است.

[1] Marc van Kreveld, Mark Overmars, and Mark de Berg. “Computational Geometry: Algorithms and Applications”. 3 rd Edition, Springer, 2008.