ساده سازی مسیرهای هندسی

دفاع آقای دانش پژوه بودیم! :)

حالت های مساله:

*حالت دو بعدی (صفحه)

*حالت دو و نیم بعدی (طول و عرض و ارتفاع): مثل حرکت روی زمین

روش های حل مساله:

*ساده سازی هموتوپیک: مسیری که می دهیم را بدون عبور از هیچ مانعی بتوان به مسیر اصلی تبدیل کرد. (در یک حالت به ازای هر قسمت از مسیر به صورت محلی این کار را می کرد و در حالت دیگر به ازای کل مسیر. فکر کنم اولی محدود بود دومی نامحدود.)

*ساده سازی با دنباله کانونی: دنباله ای که اگر مسیر از زیر یک نقطه عبور می کرد x_ و اگر از بالای آن عبور می کرد x- می گذاشتیم. با این کار دنباله را به صورت خطوط افقی و عمودی به دست می آوردیم.

*ساده سازی با مسیرهای x-یکنوا: به چند تا مسیر که بر حسب مولفه x شان یکنوا بودند تقسیم می کرد.

*ساده سازی با دید پذیری: ایده ی آن رسم شعاع از یک نقطه (نقطه شروع) بود و روی این شعاع ها تصویر می کردیم.

اینجا هم تعریف خطا در مساله تاثیر زیادی دارد (مثل داده کاوی). خطاهایی که در نظر گرفته بودند:

*اختلاف مساحت ها (مساحت جهت دار که در خود ارائه به آن گفتند مساحت قطبی ولی همان چیزی بود که ما همیشه حساب می کردیم. الآن که فکر می کنم می بینم تا حدی شبیه جمع مینکوفسکی هم هست!)

برای این کار ثابت کرده بودند که می شود مسیر را با اضافه کردن قسمت دیگری به شکل مساحت در آورد.

*ناحیه دید پذیر: تعداد پاره خطهایی که بعد از ساده سازی دیگر دیده نمی شوند.

از ایده هایی که در این زمینه توسط داورها داده شد:

*دادن تقریب برای حالتی بود که گوشه های نوک تیز داشته باشیم که مساحت کم دارند. گفتند نمی شود ولی به نظرم اگر ایده ای در مورد spanner ها جواب بدهد باید اینجا هم جواب بدهد. (این ایده ی آقای خسروی-دانشگاه تهران) بود.

*ایده ی دیگری که مطرح شد (باز هم آقای خسروی) این بود که روی  triangulated irregular network (TIN) مساله را حل کنند (کلا ایشون ایده می دادند به جای اینکه ایراد بگیرند! :دی) که البته جزو کارهایی که آقای دانش پژوه (ارائه دهنده) کرده بودند بود ولی فقط نتایج عملی داشت.

از ایرادهایی که گرفته شد:

*ایراد دکتر محدث (علوم کامپیوتر-امیرکبیر) گرفتند این بود که اگر دو نقطه x برابر داشته باشند چه کار می کنید. خود آقای دانش پژوه به عنوان ایراد این را قبول کردند اما من قبول ندارم چون ما در هندسه محاسباتی خیلی اوقات فرض general position (اینکه هیچ سه نقطه ای هم خط نباشند، هیچ چهار نقطه ای هم دایره و ..) می کنیم که استدلالمان هم این است که با اپسیلون تا جا به جا کردن نقطه می شود به این حالت رسید. با توجه به اینکه این کار ساده سازی هندسی هم بود خیلی به نظرم اپسیلون تا جا به جا کردن نقطه تاثیر نداشت.

*ایرادهای دکتر رزازی (نرم افزار -امیرکبیر) را که ما به دلیل پذیرایی نصفش را نشنیدیم ولی بیشتر در مورد ایده های اصلی کار و هدف کار بود و اینکه چرا بر حسب پارامترهای خطا تقریب ندارند که جواب آقای دانش پژوه هم این بود که تا همین حد از تضمین های تئوری در کارهای این زمینه نیست و روشی که تقریب خطاها را داده باشد اصلا نیست. (چون تقریب ها بر حسب میزان ساده سازی مسیر بود.)

*ایرادی که دکتر ضرابی زاده (استاد فعلی من!) گرفتند این بود که اگر الگوریتم را برای حالت جویبار داده استفاده می کنید باید زمان آن زیرخطی (sublinear) باشد و شما بر حسب k (تعداد نقاطی که در مسیر ساده شده از بین نقاط مسیر اصلی نگه داشته می شوند) است. جوابی که داده شد این بود که k در ورودی داده می شود که به نظر من قانع کننده نبود.

*ایراد دیگری که دکتر ضرابی زاده گرفتند این بود که شما فقط یک بار کوئری می زنید ولی به دو مرحله ی پیش پردازش و کوئری تقسیم کردید که جواب دادند برای سادگی کار بوده است.

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