Paper Info
Title
Searching A Polygonal Room With One Door By A 1-Searcher
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 P 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 P, 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(n(2))-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.
Year
DOI
Venue
2000
10.1142/S0218195900000127
INTERNATIONAL JOURNAL OF COMPUTATIONAL GEOMETRY & APPLICATIONS
Keywords
DocType
Volume
visibility, motion planning, pursuit-evasion, graph algorithm
Journal
10
Issue
ISSN
Citations 
2
0218-1959
27
PageRank 
References 
Authors
2.06
11
3
Name
Order
Citations
PageRank
Jae-Ha Lee114414.19
Sang-Min Park222321.45
Kyung-Yong Chwa391997.10