Searching for mobile intruders in circular corridors by two 1-searchers |
| |
Authors: | Bo JiangXuehou Tan |
| |
Institution: | a School of Inform. Sci. and Tech., Dalian Maritime University, Chinab School of Inform. Sci. and Tech., Tokai University, 4-1-1, Kitakaname, Hiratsuka 259-1292, Japan |
| |
Abstract: | We consider the problem of searching for a mobile intruder in a circular corridor by two mobile searchers, who hold one flashlight. A circular corridor is a polygon with one polygonal hole such that its outer and inner boundaries are mutually weakly visible. Both 1-searchers always direct their flashlights at the inner boundary. The objective is to decide whether there exists a search schedule for two 1-searchers to detect the intruder, no matter how fast he moves, and if so, generate a search schedule. We give a characterization of the circular corridors, which are searchable by two 1-searchers. Based on our characterization, an O(nlogn) time algorithm is then presented to determine the searchability of a circular corridor, where n denotes the total number of vertices of the outer and inner boundaries. Moreover, a search schedule can be reported in time linear in its size, if it exists. |
| |
Keywords: | Computational geometry Visibility Polygon search problem 1-searchers Deadlocks |
本文献已被 ScienceDirect 等数据库收录! |
|