Online Polygon Search by a Seven-State Boundary 1-Searcher

摘要

Polygon search is the problem of finding mobile intruders who move unpredictably in a polygonal region. In this paper, we consider a special case of this problem, called boundary search, where the searcher is allowed to move only along the boundary of the polygon. We concentrate on a single searcher with one flashlight (called a 1-searcher), but it is known that a single boundary 1-searcher has the same searching power as a single boundary searcher with 360° vision. Our main result is that the movement of the searcher can be controlled by a finite-state machine having only seven states. This automaton has no built-in information about the input polygon and, for any given polygon P, if P can be searched by a boundary searcher at all, then this automaton will successfully search P., no matter where on the boundary of P it is initially placed. All information about P is acquired by the automaton online, as it searches P. We also show that if P can be searched by a boundary searcher, then our automaton searches it by circling its boundary less than three times.