مشاهده مشخصات مقاله
یافتن کوتاه‌ترین مسیر برای مشاهده یک پاره‌خط در یک ناحیه چندضلعی
|
Authors |
-
الهه شبان
-
مصطفی نوری بایگی
|
|
Conference |
بیست و هفتمین کنفرانس بین الملی انجمن کامپیوتر ایران |
|
Abstract |
پیدا کردن کوتاه‌ترین مسیر برای مشاهده یک شیء یک مسأله پر‌کاربرد در هندسه محاسباتی است. از جمله کار‌بردهای آن می‌توان به وضعیتی که دیدن یا دیده شدن توسط شیء هدف اهمیت دارد اشاره کرد. به عنوان مثال هنگامی که بخواهیم با شیء هدف ارتباط برقرار کنیم یا آن را بازرسی کنیم؛ با این شرط که نحوه ارتباط با شیء هدف به صورت خط دید باشد. نقطه مبدأ s را در یک ناحیه چندضلعی P با h-1 مانع در نظر بگیرید. می‌خواهیم با انجام پیش‌پردازش بر روی ورودی، کوتاه‌ترین مسیر از نقطه s به نقطه دلخواهی در P را پیدا کنیم؛ به طوری که پاره‌خط دلخواه l از آن نقطه قابل دیدن باشد.
برای حل این مسأله در این مقاله ما دو راه حل ارائه کردیم. در راه حل نخست با صرف زمان پیش‌پردازش O(n4+ɛ) مسأله در زمان O(nh) قابل حل خواهد بود. در راه حل پیشنهادی دوم با افزایش زمان پیش‌پردازش به O(n8) توانستیم مسأله را در زمان O(logn) حل کنیم. |
|
قیمت |
-
برای اعضای سایت : 100,000 Rial
-
برای دانشجویان عضو انجمن : 20,000 Rial
-
برای اعضای عادی انجمن : 40,000 Rial
|
خرید مقاله
|
|
.gif){kind=icon}