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.
My Menu
Saved Items

Searching a Circular Corridor with Two Flashlights

Bo Jiang18 and Xuehou Tan18, 19 Contact Information

(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.

Contact Information Xuehou Tan
Email: tan@wing.ncc.u-tokai.ac.jp
Fulltext Preview (Small, Large)
Image of the first page of the fulltext

References secured to subscribers.



Export this chapter
Export this chapter as RIS | Text
 
Remote Address: 38.107.191.110 • Server: mpweb06
HTTP User Agent: CCBot/1.0 (+http://www.commoncrawl.org/bot.html)