Characterization of Boundary 1-Searcher for Polygons
Peng Li · Hu'nan Shifan Daxue xuebao. Ziran kexue ban · 2010
The polygon searching is the problem of finding a mobile intruder in a polygonal region where the intruder's moving path and moving speed are unpredictable.The problem of searching a simple polygonal region with a boundary 1-searcher is considered,and the necessary and sufficient conditions for testing the searchablity of polygons are proposed.It is showed that if a polygon is searchable by a boundary 1-searcher can be detected in O(n) time and space by using these conditions.The results improve the previous O(nlogn) time bounds.At the same time,some known proving processes are simplified.