We study the problem of searching for a mobile intruder in a polygonal region P by two guards. The objective is to decide whether there should exist a search schedule for the two guards to detect the intruder, no matter how fast the intruder moves, and if so, generate a search schedule. During the search, the two guards are required to walk on the boundary of P continuously and be mutually visible all the time. We present a characterization of the class of polygons searchable by two guards in terms of non-redundant components, and thus solve a long-standing open problem in computational geometry. Also, we give an optimal O(n) time algorithm to determine the two-guard searchability in a polygon, and an O(nlog n+m) time algorithm to generate a search schedule, if it exists, where n is the number of vertices of P and m (≤n2) is the number of search instructions reported.
展开▼
