Simple Characterization of Polygons Searchable by 1-Searcher
Tsunehiko Kameda, John Z. Zhang, Masafumi Yamashita · 2006
Suppose intruders are in a dark polygonal room and they can move arbitrarily fast, trying to avoid detection. A boundary 1-searcher can move along the polygon boundary, equipped with a flash light that she can direct in any direction. A polygon is searchable if there is a schedule for the searcher in order to detect the intruders no matter how they move. We identify three simple forbidden patterns such that a given polygon is searchable by a boundary 1-searcher if and only if it has none of them. The concept of sweeping the visibility diagram greatly facilitates the proof. 1