یافتن کوتاه ترین مسیر برای مشاهده یک پاره خط در یک ناحیه چندضلعی

پیدا کردن کوتاه ترین مسیر برای مشاهده یک شیء یک مساله پرکاربرد در هندسه محاسباتی است. از جمله کاربردهای آن میتوان به وضعیتی که دیدن یا دیده شدن توسط شیء هدف اهمیت دارد اشاره کرد. به عنوان مثال هنگامی که بخواهیم با شیء هدف ارتباط برقرار کنیم یا آن را بازرسی کنیم؛ با این شرط که نحوه ارتباط با شیء هدف به صورت خط دید باشد. نقطه مبدا s را در یک ناحیه چندضلعی P باh-۱ مانع در نظر بگیرید. میخواهیم با انجام پیش پردازش بر روی ورودی، کوتاه ترین مسیر از نقطه s به نقطه دلخواهی درP را پیدا کنیم؛ به طوری که پاره خط دلخواه l از آن نقطه قابل دیدن باشد.برای حل این مساله در این مقاله ما دو راه حل ارائه کردیم. در راه حل نخست با صرف زمان پیش پردازش ( O(n۴+ مساله در زمان O nh قابل حل خواهد بود. در راه حل پیشنهادی دوم با افزایش زمان پیشپردازش به O n۸ توانستیم مساله را در زمان O logn حل کنیم.

Keywords:

کوتاه ترین مسیر , دیدن , ناحیه چندضلعی