Searching for mobile intruders in circular corridors by two 1-searchers
Searching for mobile intruders in circular corridors by two 1-searchers
复制标题
DOI：
10.1016/j.dam.2010.10.007
复制
发表时间：
2011-09
期刊：
影响因子：
--
通讯作者：
Bo Jiang;X. Tan
中科院分区：
文献类型：
--
作者：
Bo Jiang;X. Tan
研究了两个移动的搜索者在圆形走廊中搜索一个移动的入侵者的问题。圆形走廊是带有一个多边形孔的多边形，其外部边界和内部边界相互弱可见。两个1-搜索者总是把手电筒对准内边界。目标是决定是否存在一个搜索时间表，两个1-搜索检测入侵者，无论他移动得多快，如果是这样，生成一个搜索时间表。我们给出了一个表征的圆形走廊，这是可搜索的两个1-搜索。基于我们的特征，然后提出了一个O（nlogn）的时间算法来确定一个圆形走廊的可搜索性，其中n表示的外，内边界的顶点总数。此外，搜索时间表可以在其大小的时间线性报告，如果它存在的话。
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.