SEARCHING A POLYGONAL ROOM WITH ONE DOOR BY A 1-SEARCHER
Authors:
- 30 April 2000
- journal article
- research article
- Published by World Scientific Pub Co Pte Ltd in International Journal of Computational Geometry & Applications
- Vol. 10 (02) , 201-220
Abstract
The 1-searcher is a mobile guard whose visibility is limited to a ray emanating from his position, where the direction of the ray can be changed continuously with bounded angular rotation speed. Given a polygonal region [Formula: see text] with a specified boundary point d, is it possible for a 1-searcher to eventually see a mobile intruder that is arbitrarily faster than the searcher within [Formula: see text], before the intruder reaches d? We decide this question in O (n log n)-time for an n-sided polygon. Our main result is a simple characterization of the class of polygons (with a boundary point d) that admits such a search strategy. We also present a simple O(n2)-time algorithm for constructing a search schedule, if one exists. Finally, we compare the search capability of a 1-searcher with that of two guards.Keywords
This publication has 8 references indexed in Scilit:
- Bushiness and a tight worst-case upper bound on the search number of a simple polygonInformation Processing Letters, 1998
- Two-Guard Walkability of Simple PolygonsInternational Journal of Computational Geometry & Applications, 1998
- AN OPTIMAL ALGORITHM FOR THE TWO-GUARD PROBLEMInternational Journal of Computational Geometry & Applications, 1996
- SEARCHING FOR A MOBILE INTRUDER IN A CORRIDOR —THE OPEN EDGE VARIANT OF THE POLYGON SEARCH PROBLEMInternational Journal of Computational Geometry & Applications, 1995
- Searching for a Mobile Intruder in a Polygonal RegionSIAM Journal on Computing, 1992
- THE TWO GUARDS PROBLEMInternational Journal of Computational Geometry & Applications, 1992
- The Searchlight Scheduling ProblemSIAM Journal on Computing, 1990
- Linear-time algorithms for visibility and shortest path problems inside triangulated simple polygonsAlgorithmica, 1987