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

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

• آزمون‌های میان‌ترم و پایان‌ترم (۱۰ نمره)
• سه تمرین‌ نظری (۶ نمره)
• پروژه‌ی پژوهشی (۴ نمره)