تعقیب و گریز در چندضلعی با مانع

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