هندسه ی محاسباتی

هدف از اين نوشتار مقدمه ای ساده و تا حد امکان کامل بر هندسه ی محاسباتی می باشد. مخاطبان اصلی مورد نظر من اين سری از نوشته ها شرکت کنندگان در مسابقات الگوريتمی (مانند ACM ICPC، Topcoder، …) می باشد، ولی احتمالا اين نوشته ها می تواند مورد استفاده ی طيف وسيعی از دانشجويان رشته های مرتبط با علوم کامپيوتر قرار بگيرد.

دلايل اصلی من برای نوشتن اين نوشته ها:

• هيچ منبع فارسی ای را نمی شناسم که به طور گسترده به اين موضوع پرداخته باشد.
• اکثر دانشی که من در اين رابطه کسب کردم از طريق منابع مختلف (و نه منبع واحد) بوده است.
• خُب، علاقه دارم

1. مقدمات
2. پيدا کردن مساحت چندضلعی
   1. پيدا کردن فاصله ی يک نقطه از يک خط
3. آيا نقطه ی مورد نظر داخل چندضلعی است؟
4. تقاطع خطوط
5. هندسه ی محاسباتی با استفاده از اعداد مختلط
6. تبديل های هندسی (دوران، جابجايي، تغيير اندازه)
7. مساله ی پوش محدب (Convex Hull)
8. مساله های نزديکی
9. تقسيم چندضلعی به تعدادی مثلث
10. محدود کننده ها برای چندضلعی ها و مجموعه نقاط