Visibility-based pursuit-evasion in a polygonal room with a door
Jaeha Lee, Sung Yong Shin, Kyung‐Yong Chwa · 1999
Visibility-based pursuit-evasion problems are as follows: given a polygonal region, one or more searchers with visibility, and an unpredictable intruder that is arbitrarily faster than the searcher, plan the motion of the searchers so as to see the intruder.In this paper, we consider several visibility-based pursuit-evasion problems with a single searcher: l Given a simple polygon with a door (i.e., penetrable vertex) d, can a searcher find an intruder within the polygon in such a way that the intruder couldn't make a dash for the door d? l Given a simple polygon with a door d, can a searcher make no undetected intruder remain in the polygon (that is, find the intruder or evict it from the polygon through d)? l Given a building (represented as a sequence of simple polygons joined by staircases), can the searcher find the intruder within it?For each of the three problems above, we give a characterization of the class of regions that admits a search strategy and present an O(n2)-time algorithm for constructing a search path, if one exists, for an n-sided region.Interestingly, our characterizations imply that each of the above regions searchable by a searcher with omnidirectional vision (i.e., 360' vision) is also searchable by a searcher with two flashlights (i.e., ray visions).As a by-product, we improves the time complexity of the corridor search problem in [2], by a factor of log n. *This work was partially supported by KOSEF 98-0102-07-01-3.permission lo make digital or hard copies of all