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

دو شخص و در مسیرهای مشخص روی مرز ضلعی ساده حرکت می کنند. شخص سرعت خود را طوری کنترل میکند که در طول مسیر، توسط شخصدیده نشود. مجموعه شامل نقطه درون به عنوان مانع دید داده شده و فرض براین است که سرعت زاوی های چرخش دو نفر حول هر مانع ثابت است. هدف مسئله، تعیین مسیر امن برای هر دو پیماینده است به طوری کههرگز همدیگر را در طول مسیر نبینند. برای یافتن چنین مسیری از نمودار رویت پذیری استفاده شده است. نمودار رویت پذیری، رویت پذیر بودن دو نقطه را در یک چند ضلعی ساده نشان میدهد. همچنین به عنوان تعمیمی ازمسئله تعقیب و گریز با مانع، حالتی را مورد مطالعه قرار می دهیم که در آن شخص باید سرعت خود را طوری کنترل کند که در طول مسیر توسط پیماینده دیده نشود. با استفاده از نمودار رویت پذیری شخص با هریک ازپیمانده، شخص با پیمانده میتواند مسیر امنی داشته باشد. همچنین نشان می دهیم یافتن چنین مسیری در مرتبه زمانی امکان پذیر است. الگوریتم هایهندسی همچون رویت پذیری با رو شهای هندسی به حل مسائل پیچیده دنیایی واقعی می پردازند به طوری که می توان مسائل با محدودیت و تعامل بین حافظه و زمان اجرا به صورت هوشمندانه حل نمود.