الگوریتمی سریع برای پوشش دید مستطیلی چندضلعی های متعامد ساده با حداقل تعداد r-Star ها

این مقاله الگوریتمی برای پوشش دید چندضلعی های متعامد ساده با حداقل تعداد نگهبانان ارائه می دهد. در واقع حداقل تعداد نگهبان را برای چندضلعی های ساده (بدون حفره) متعامد برای همه حالات بررسی کرده و قادر خواهیم بود که برای هر یک از نگهبانان نیز محدوده مستطیل شکلی را بیابیم. به عبارت دیگر ما مساله پوشش چندضلعی های متعامد ساده را با حداقل r-Star ها را بررسی می کنیم. در هر چندضلعی متعامد P دو نقطه p و q ، نسبت به هم r-visible هستند اگر و فقط اگر آن دو نقطه را دو گوشه مخالف مستطیلی در نظر بگیریم، تمام مستطیل درون چندضلعی P قرار داشته باشد. حال یک چندضلعی P را یک r-Star گوییم اگر یک نقطه p در آن وجود داشته باشد به طوریکه هر نقطه q عضو چندضلعی، از p ، r-visible باشد. در این مقاله ما الگوریتمی را پیشنهاد می کنیم که بر روی کلیه چندضلعی های ساده متعامد کاربرد دارد و قادر است حداقل تعداد نگهبانان را در جای خود مستقر کند. این الگوریتم با استفاده از روشی به نام مستطیل بندی (تقسیم چندضلعی متعامد به تعدادی مستطیل) ، تعدادی از r-Star ها را افراز کرده و به پردازش آنها جهت درج نگهبانان در محل خود برای رسیدن به هدف، که حداقل تعداد نگهبانان است می پردازد. الگوریتم پیشنهادی ما قادر است تا در زمان حداقل تعداد نگهبانان را به همراه محدوده مستطیل شکلی برای آنها تعیین کند در حالی که مرتبه اجرایی بهترین الگوریتم های موجود قبلی بوده است. از دیگر مزایای این الگوریتم می توان به نداشتن محدودیت در چندضلعی های متعامد ساده اشاره کرد.