کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
419858 | 683868 | 2011 | 13 صفحه PDF | دانلود رایگان |
![عکس صفحه اول مقاله: Searching for mobile intruders in circular corridors by two 1-searchers Searching for mobile intruders in circular corridors by two 1-searchers](/preview/png/419858.png)
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)O(nlogn) time algorithm is then presented to determine the searchability of a circular corridor, where nn 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.
Journal: Discrete Applied Mathematics - Volume 159, Issue 16, 28 September 2011, Pages 1793–1805