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

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

هندسه محاسباتی چیه و چی نیست؟

میشه گفت هندسه محاسباتی یکی از زیرشاخه‌های الگوریتمه و در اون هدف ما اینه که مسائل هندسی رو با کامپیوتر حل کنیم. توجه داشته باشید که منظور از هندسه در اینجا هندسه اقلیدسی هست و هیچ خبری از هندسه‌های نااقلیدسی، هندسه دیفرانسیل، هندسه جبری و ... نیست. اینها صرفاً در کلمه هندســــــــه با هم مشترک هستن (البته جریان غالب رو عرض می‌کنم). وقتی هم که صحبت از حل مسأله با کامپیوتر و الگوریتم هست، یعنی شما ورودی مشخصی داشته باشید و بعد خروجی مشخصی هم بخواید. مثلاً می‌تونید مختصـــات یک سری نقطه رو در صفحه بدید و بعد به عنوان خروجی کوچکترین چندضلعی دربرگیرنده این نقاط رو بخواید (اصطلاحاً پوش محدب). برای دیدن مثال‌های بیشتر، صفحه‌ی ویکی‌پدیای هندسه محاسباتی رو نگاه کنید.

پیش‌نیازش چیه؟

می‌تونید هندسه محاسباتی رو مثل چای در نظر بگیرید و ساختمان‌داده و الگوریتم رو مثل قند و نبات! دیگه نیاز به توضیح نداره که چـــــای چقدر با قند و نبات دلچسب و خوبه و بدون اونها تلــــــــخ و افتضــــــــــاح. البته شیـــرینی ساختمان‌داده و الگــــــــوریتم قرار نیست گلوتون رو بزنه و ربطی به دیابت هم نداره، پس تا جایی که می‌تونیــــــــد ساختمان‌داده و الگـــــــوریتم بلد باشید. علاوه بر ساختمان‌داده‌های معمول، یک سری ساختمان‌داده در هندسه محاسباتی بسیار کاربرد دارن (مثل DCEL، Range tree، Segment tree، Interval tree و Quadtree) که در یک درس مقدماتیِ هندسه محاسباتی دست‌کم یکی دوتاش رو معرفی می‌کنن.

از کجا یاد بگیریم؟

• آشنایی اولیه: فصل 33 از کتاب Introduction to Algorithms معروف به CLRS
• کتاب شناخته‌شده دی‌برگ و دیگران «Computational Geometry; Algorithms and Applications» که دو ترجمه ناقص به فارسی ازشون وجود داره. یکی ترجمه بهرام صادقی و مصطفی عباسی‌کیا و دیگری ترجمه مهدی ایمان‌پرست که من خودم اولی رو داشتم. به نظرم خوندن کتاب انگلیسیــــــــــش خیلی بهتر بود. غالباً هندسه محاسباتی رو از روی همین کتاب درس میدن.
• جزوه‌ی آقای دیوید ماونت (David Mount) که اگر اسمـــــــشون رو با Computational geometry جستجو کنید، به راحتی پیدا میشه. این جزوه خیلی از مباحث هندسه محاسباتی رو پوشش میده و مختصر و مفید هم هست.
• فیلم‌های مدرسه زمستانی هندسه محاسباتی (wscg) که سال 97 در دانشگاه امیرکبیر برگزار شده و خیلی از مباحث مختلف هندسه محاسباتی رو در برمی‌گیره و تقریباً بهترین استادانی که در کشور روی این موضوع کار می‌کنن، در این مدرسه ارائه داشتن.

از هندسه محاسبــــاتی موضوعی که من بهش مشغول شدم، گراف‌های قابلیت دید (Visibility Graphs) هست. اولین بار در کنفرانسی در مورد کاربردهای نظریه گراف با این موضوع آشنا شدم. چیزی که برام جالب بود، ساده و قابل فهم بودن صورتِ مسائلی بود که در این زمینه همــــچنان حل نشده باقی موندن (منظورم از سادگی اینه که صورت مسأله‌ها رو یک دانش‌آموز دبیرستانی راحت می‌تونه متوجه بشه). برای سمـــــینار دوره ارشد، روی مقاله‌ی زیر کار می‌کردم که به دسته‌بندی مسائل حل نشده گراف‌های قابلیت دید می‌پرداخت و بعد برای پایان‌نامه هم از همین مقاله الهام گرفتم:

Subir K. Ghosh and Partha P. Goswami. 2013. Unsolved problems in visibility graphs of points, segments, and polygons

در پایان باید بگم هدف این نوشته این بود که آشنایی و یادگیری هندسه محاسباتی رو آسون‌تر کنه. بنابراین اگر منابع خوب دیگری در این زمینه می‌شناسید (از فیلم دوره درسی گرفته تا حل تمرین کتاب‌های مختلف یا موارد دیگه)، حتماً معرفی کنید که بقیه استفاده کنن.

به امیدِ چشیدن شیرینی دانستن!

محمدرضا شمس اشکذری

تیرِ صفر یک

و سپاس خدای را ...