Simple algorithms for searching a polygon with flashlights

The k- searcher is a mobile guard whose visibility is limited to k rays emanating from her position, where the direction of each ray can be changed continuously with bounded angular rotation speed. Given a polygonal region P, is it possible for the k-searcher to eventually see a mobile intruder that...

Full description

Saved in:
Bibliographic Details
Published in:Information processing letters 2002-03, Vol.81 (5), p.265-270
Main Authors: Lee, Jae-Ha, Park, Sang-Min, Chwa, Kyung-Yong
Format: Article
Language:English
Subjects:
Algorithms
Applied sciences
Artificial intelligence
Combinatorics
Combinatorics. Ordered structures
Computational geometry
Computer science
control theory
systems
Convex and discrete geometry
Exact sciences and technology
Geometry
Graph algorithms
Graph theory
Graphs
Mathematics
Methods of scientific computing (including symbolic computation, algebraic computation)
Numerical analysis. Scientific computation
Path planning
Pattern recognition. Digital image processing. Computational geometry
Sciences and techniques of general use
Studies
Visibility
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:The k- searcher is a mobile guard whose visibility is limited to k rays emanating from her position, where the direction of each ray can be changed continuously with bounded angular rotation speed. Given a polygonal region P, is it possible for the k-searcher to eventually see a mobile intruder that is arbitrarily faster than the searcher within P? We present O( n 2)-time algorithms for constructing a search schedule of the 1-searcher and the 2-searcher, respectively. Our framework for the 1-searcher can be viewed as a modification of that of LaValle et al. [Proc. 16th ACM Symp. on Computational Geometry, 2000, pp. 260–269] and is naturally extended for the 2-searcher.
ISSN:0020-0190
1872-6119
DOI:10.1016/S0020-0190(01)00235-6