1
استادیار گروه علوم کامپیوتر، دانشکده علوم ریاضی، دانشگاه الزهرا، تهران، ایران
2
مربی گروه کامپیوتر، ، دانشکده علوم پایه و فنی، دانشگاه کوثر بجنورد، ایران.
چکیده
دو شخص A و B در مسیرهای مشخص روی مرز n ضلعی ساده P حرکت می‌کنند. شخص A سرعت خود را طوری کنترل می‌کند که در طول مسیر، توسط شخص B دیده نشود. مجموعه S شامل k نقطه درون P به عنوان مانع دید داده شده و فرض براین است که سرعت زاویه‌ای چرخش دو نفر حول هر مانع ثابت است. هدف مسئله، تعیین مسیر امن برای هر دو پیماینده است به طوری که هرگز همدیگر را در طول مسیر نبینند. برای یافتن چنین مسیری از نمودار رویت‌پذیری استفاده شده است. نمودار رویت‌پذیری، رویت‌پذیر بودن دو نقطه را در یک چند ضلعی ساده نشان می‌دهد. همچنین به عنوان تعمیمی از مسئله تعقیب و گریز با مانع، حالتی را مورد مطالعه قرار می‌دهیم که در آن شخص A باید سرعت خود را طوری کنترل کند که در طول مسیر توسط m پیماینده دیده نشود. با استفاده از نمودار رویت‌پذیری شخص A با هریک از m پیمانده، شخص A با m پیمانده می‌تواند مسیر امنی داشته باشد. همچنین نشان می‌دهیم یافتن چنین مسیری در مرتبه زمانی O(m^2 n^3 log mn) امکان پذیر است. الگوریتم‌های هندسی همچون رویت‌پذیری با روش‌های هندسی به حل مسائل پیچیده دنیایی واقعی می‌پردازند به‌طوری که می‌توان مسائل با محدودیت و تعامل بین حافظه و زمان اجرا به صورت هوشمندانه حل نمود.
)