Searching a Polygonal Region by a Boundary Searcher

This paper considers the problem of planning the motion of a searcher in a polygonal region to eventually "see" an intruder that is unpredictable and capable of moving arbitrarily fast. A searcher is called the \it boundary searcher if he continuously moves on the polygon boundary and can see only along the rays of the flashlights he holds at a time. We present necessary and sufficient conditions for an n-sided polygon to be searchable by a boundary searcher. Based on our characterization, the equivalence of the ability of the searchers having only one flashlight and the one of the searchers having full vision is simply established, and moreover, an optimal time and space algorithm for determining the searchability of simple polygons is obtained. We also give an time algorithm for generating a search schedule if it exists, where I is the number of search instructions reported. Our results improve upon the previously known time and space bounds.