AN ALGORITHM FOR SEARCHING A POLYGONAL REGION WITH A FLASHLIGHT
Authors:
- 1 February 2002
- journal article
- research article
- Published by World Scientific Pub Co Pte Ltd in International Journal of Computational Geometry & Applications
- Vol. 12 (01n02) , 87-113
Abstract
We present an algorithm for a single pursuer with one flashlight searching for an unpredictable, moving target in a 2D environment. The algorithm decides whether a simple polygon with n edges and m concave regions can be cleared by the pursuer, and if so, constructs a search schedule of length O(m) in time O(m2+m log n+n). The key ideas in this algorithm include a representation called "visibility obstruction diagram" and its "skeleton": a combinatorial decomposition based on a number of critical visibility events. An implementation is presented along with a computed example.Keywords
This publication has 6 references indexed in Scilit:
- 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
- A Pedestrian Approach to Ray Shooting: Shoot a Ray, Take a WalkJournal of Algorithms, 1995
- Ray shooting in polygons using geodesic triangulationsAlgorithmica, 1994
- Searching for a Mobile Intruder in a Polygonal RegionSIAM Journal on Computing, 1992
- THE TWO GUARDS PROBLEMInternational Journal of Computational Geometry & Applications, 1992