Searching a Polygonal Region by Two Guards

摘要

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 exists a search schedule for two guards to detect the intruder, no matter how fast he moves, and if so, generate a search schedule. During the search, 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, and give an optimal O(n) time algorithm for determining the two-guard searchability of a polygon and an algorithm for generating a search schedule in time linear in its size.