SEARCHING A ROOM BY TWO GUARDS
Sang‐Min Park, Jaeha Lee, Kyung‐Yong Chwa · International Journal of Computational Geometry & Applications · 2002
We consider the problem of searching for mobile intruders in a polygonal region with one door by two guards. Given a simple polygon [Formula: see text] with a door d, which is called a room [Formula: see text], two guards start at d and walk along the boundary of [Formula: see text] to detect a mobile intruder with a laser beam between the two guards. During the walk, two guards are required to be mutually visible all the time and eventually meet at one point. We give a characterization of the class of rooms searchable by two guards and an O(n log n)-time algorithm to test if a given room admits a walk, where n is the number of the vertices in [Formula: see text].