Searching for Mobile Intruders in Circular Corridors by Three 1- Searchers

ABSTRACT

We consider the problem of searching for a mobile intruder in a circular corridor by three mobile searchers, who hold one flashlight, a variation of the 1-searcher problem in a circular corridor. A circular corridor is a polygon with one polygonal hole such that its outer and inner boundaries are mutually weakly visible. The 1-searcher has a flashlight and can see only along the ray of the flashlight emanating from his position. In the searching process, each 1-searcher can move on the boundary or into the circular corridor, the beam of his flashlight must be irradiated on the inner boundary. The previous research of this paper suggests an algorithm which decides whether a given circular corridor is searchable by two 1-searchers or not. This paper proves that three 1-searchers always clear a given circular corridor. And a search schedule can be reported in O(m) time, where m≤n² denotes the walk instructions reported, and n denotes the total number of vertices of the outer and inner boundaries.

Keywords: