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

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

• آزمون: آزمون‌های میان‌نیم‌سال و پایان‌نیم‌سال (۵۵ درصد نمره)
• تمرین: سه تمرین نظری (۲۵ درصد نمره)
• پروژه: پروژه‌ی پژوهشی (۲۰ درصد نمره)