مسئله قابل دید بودن رئوس موانع از یک نقطه یکی از مسائل معروف در حوزه هندسه محاسباتی است. در این مقاله ما تعریفی جدید از قابلیت دید بین دو نقطه ارائه می‌کنیم که در مسیریابی دسته‌ای خاص از ربات‌ها کاربرد دارد. در این تعریف دو نقطه نسبت به هم قابل دید هستند اگر زنجیره‌ای از پاره‌خط‌ها بین دو نقطه با حداکثر زاویه شکست محدود و رعایت حداقل فاصله بین دو شکست متوالی وجود داشته باشد که هیچ پاره‌خطی از این زنجیره با هیچ‌یک از یال‌های موانع برخورد نکند. سپس در ادامه الگوریتمی برای تعیین رئوس قابل دید از یک نقطه را بر اساس تعریف جدید ارائه می‌کنیم. نشان خواهیم داد با صرف زمان $O(n^\frac{4}{3} \log^c n)$ و حافظه $O(n^\frac{4}{3})$ می‌توان مسأله را حل کرد. در این رابطه‌ها $n$ تعداد رئوس مانع و $c$ یک عدد ثابت است. همچنین نشان می‌دهیم در صورتی که موانع از قبل مشخص باشند، می‌توان داده‌ساختاری را در مدت زمان $O(b \log^c)$ و با حافظه $O(b)$ تهیه کرد که با دریافت نقطه ناظر در زمان پرس‌وجو، رئوس قابل دید از نقطه را در زمان $O(n^2 \log^c n / \sqrt b)$ محاسبه کند. در این رابطه‌ها $b$ یک پارامتر دلخواه است که در شرط $n^\frac{4}{3} \le b \le n^2$ صدق می‌کند.

کلمات کلیدی