Welcome!
To use the personalized features of this site, please log in or register.
If you have forgotten your username or password, we can help.
|
 |
Searching a Circular Corridor with Two Flashlights
| |
|
Searching a Circular Corridor with Two Flashlights
Bo Jiang18 and Xuehou Tan18, 19 
| (18) |
School of Inform. Sci. and Tech., Dalian Martime University, China |
| (19) |
Tokai University, 317 Nishino, Numazu 410-0395, Japan |
Abstract
We consider the problem of searching for a mobile intruder in a circular corridor (a polygon with one polygonal hole) by two searchers, who hold a flashlight. Both searchers move on the outer boundary, directing
their flashlights at the inner boundary. The objective is to decide whether there exists a search schedule for the searchers to detect the intruder, no matter how fast he moves. We give a characterization of the class of circular
corridors, which are searchable with two flashlights. Based on our characterization, an O(n logn) time algorithm is then presented to determine the searchability of a circular corridor with two flashlights, where n denotes the total number of vertices of the outer and inner boundaries. Moreover, a search schedule can be output in time
linear in its size, if it exists. Our result gives the first efficient solution to the polygon search problem for two searchers.
Fulltext Preview (Small, Large)
 References secured to subscribers.
|
|
|
|
|
|