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