Solving Linear Programs in the Current Matrix Multiplication Time

https://arxiv.org/pdf/1810.07896.pdf

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

منبع: https://conference.imp.fu-berlin.de/eurocg18/download/paper_25.pdf

یکی از مسئله‌های مشهور هندسه محاسباتی ساده‌سازی مسیر است. هر چند که اکثراً در فیلدهای دیگر از آن استفاده می‌کنند.
در این مسئله یک دنباله از نقاط به ما داده شده است و هدف این است که یک زیردنباله از آن را انتخاب کنیم به طوری که فاصله‌ی بین مسیر اولیه و مسیر ساده شده کمینه بشود. ملاک‌های فاصله‌ی زیادی بین مسیرها تعریف شده‌اند، مثل فاصله عمودی، فاصله هاسدورف، فاصله فرشه.
یکی از الگوریتم‌های مشهور در این زمینه الگوریتم Imai-Iri بود که روی رأسهای مسیر یک گراف می‌ساخت که وزن یال‌های آن فاصله‌ی بین خط مستقیم بین دو رأس با دنباله‌ای بود که شروع و پایانش دو سر این یال بودند.
در فاصله‌ی فرشه، ما سرعت حرکتمان روی مسیرها را تغییر می‌دهیم به طوری که بیشترین فاصله‌ی بین دو نقطه متناظر مسیرها مینیمم بشود. اکثراً این تعریف را با دو تا متحرک که هر کدام روی یکی از این مسیرها حرکت می‌کنند نشان می‌دهند. من خودم پیشنهادم اسب/خر و صاحبش است که طول افسار می‌شود فاصله‌ی فرشه. ولی در نسخه‌ی خارجی مسئله سگ و طناب متصل به قلاده‌اش است.
حالا نکته‌ای که در مورد این مسئله پیش می‌آید این است که جواب Imai-Iri الزاماً بهینه نیست. یعنی درست است که ما فقط اجازه داریم از یالهای مسیر استفاده کنیم، اما ممکن است فاصله‌ی فرشه بین یک رأس و یک نقطه روی یک یال رخ بدهد.

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

سوالی که به نظرم جا دارد روی آن بیشتر بحث بشود این است که اگر اجازه داشته باشیم خودمان روی یک نقطه از مسیرهای قبلی رأس اضافه کنیم، آیا می‌شود ساده‌سازی با طول کمتری پیدا کرد یا نه؟

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