یکی از مباحثی که خیلی من رو شیفته خودش کرده هندسه محاسباتی هست. هندسه جزو درس هایی بود که در دوران دبیرستان هم برام شیرین بود. به نظرم هندسه توش یه هنری پنهان است که شاید در باقی جاهای ریاضی نشه اون رو به وضوح دید. یکی دیگه از دلایلی که هندسه به نظرم جذابه اینه که میشه مساله رو به صورت شهودی دید و روش حرف زد. به نظرم علاقه ام به هندسه یکم بخاطر ژن ایرانیمم هست چون ایرانی ها همیشه توی هندسه خیلی قوی بودن و این رو تاریخ و آثار تاریخیمون نشون میده. به هر حال من با سرچ هایی که کردم محتواهای مناسبی در باره هندسه محاسباتی ندیدم به زبان فارسی برای همین تصمیم گرفتم بیام توی ویرگول و از این دانش براتون بنویسم.
تعریف هندسه محاسباتی مسایل الگوریتمی در فضای هندسی هستش. مثلا میخوای بدونی که یک ربات را در کجا قرار بدی تا بتونی به یه سری نقطه که در صفحه هست نزدیکترین فاصله را داشته باشه. یکی دیگه از کاربردهای هندسه محاسباتی در نقشه های GIS دیده میشه حتی در زیست و ساخت داروها هم از هندسه محاسباتی استفاده میشه. در ادامه به تعریف های ابتدایی استفاده شده در هندسه محاسباتی پرداخته میشه.
نمیدونم ولی فارسی نوشتن یه سری تعریف ها شاید کلا تعریف رو بر هم بزنه واسه همین بهتره بعد از خوندن این مطلب برید و به انگلیسی سرچش کنید. پوش محدب که میشه convex hull یک تعریف پایه برای مساله هندسه محاسباتی هست. به این صورت تعریف میشه که: کوچکترین کانوکسی که یه سری نقاط در صفحه رو می پوشونه.
برای درک بهتر براتون یه عکس گذاشتم. همان طور که در عکس میبینید پوش محدب برای این نقاط میشه عکس سمت راستی.
یک تعریف خیلی جالب برای درک کانوکس هال این هست که فرض کنید اون نقاط سمت چپ میخ باشه که زدیم توی یک تخته! مثل صفحه ای که مرتاض های هندی روش میخوابند! بعد یک کش رو بندازیم دور اون میخ ها و هرجا وایستاد میشه همون پوش محدب یا convex hull مون! به اون نقطه هایی که روی شکل با p1 تا p2 نوشته شده هم میگند extreme point (دیگه واقعا فارسی این چی میشه؟?)
خب این ها تا الان یه معرفی کلی از هندسه محاسباتی بود که در ادامه به معرفی یکی از حوزه‌های هندسه محاسباتی توضیح می دم.
مساله گالری هنر برمیگرده به ۴۰ سال پیش و مساله خیلی قدیمی هست. این مساله دنبال بهینه کردن تعداد نگهبان ها برای نگهبانی از یک محیط هست. در این مساله دنبال این هستیم که نقاط بهینه ای را در چندضلعی پیدا کنیم که نقاط روی چندضلعی و نقاط درون آن قابل رویت باشند.
دو نقطه در یک چند ضلعی رویت پذیر هستند اگر پاره خطی که این دو را به هم متصل میکنند در داخل چند ضلعی قرار بگیرند. من توی ذهنم این جوری فرض میکنم که این دو تا نقطه بتونن همدیگه رو ببینند یعنی روی خط مستقیم بتونند هم رو ببینند.
چون با گذشت زمان و پیشرفت علم ما نگهبانی هامون رو به روباتها میدیم برای همین بهتره که الگوریتم های نگهبانی رو با توجه به محدودیت های حرکتی روبات ها تعریف کنیم. برای همین رویت پذیری متعامد معرفی شده. رویت پذیری متعامد یعنی دو تا نقطه رویت پذیر متعامد هستند که این دو نقطه در روی یک قطر مستطیل گذشته شده از این دو نقطه باشند و این مستطیل کامل در چندضلعی متعامد قرار بگیرد.
در این نوشته من مقدماتی درباره هندسه محاسباتی گفتم. اینکه کلا این فیلد از ریاضیات به چه چیزی می پردازه و یه سری تعاریف اصلی و پایه گفتم و دو تا تعریف از رویت پذیری.
در نوشته های آینده بیشتر راجع به این مبحث حرف میزنم. یعنی قسمت رویت پذیری متعامد.
منابعی که استفاده کردم : فیلم مدرسه زمستانی هندسه محاسباتی از دکتر ضرابی زاده و مقالات نوشته شده درباره رویت پذیری متعامد هست.
