Searching a Polygonal Region by Two Guards

We study the problem of searching for a mobile intruder in apolygonal region P by two guards. The objective is to decide whetherthere should exist a \it 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 onthe boundary of P continuously and be mutually visible all the time.We present a characterization of the class of polygonssearchable by two guards in terms of non-redundant components, andthus solve a long-standing open problem in computational geometry.Also, we give an optimal O(n) time algorithm to determine thetwo-guard searchability in a polygon, and an O(n \log n + m) timealgorithm to generate a search schedule, if it exists, where n is thenumber of vertices of P and m (\le n^2) is the number of searchinstructions reported.