Searching a polygonal room with one door by a 1-searcher

Abstract

The 1-searcher is a mobile guard whose visibility is limited to a ray emanating from his position, where the direction of the ray can be changed continuously with bounded angular rotation speed. Given a polygonal region P with a specified boundary point d, is it possible for a 1-searcher to eventually see a mobile intruder that is arbitrarily faster than the searcher within P, before the intruder reaches d? We decide this question in O(n log n)-time for an n-sided polygon. Our main result is a simple characterization of the class of polygons (with a boundary point d) that admits such a search strategy. We also present a simple O(n(2))-time algorithm for constructing a search schedule, if one exists. Finally, we compare the search capability of a 1-searcher with that of two guards.