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