Efficient Algorithms for Searching a Polygonal Room with a Door
Efficient Algorithms for Searching a Polygonal Room with a Door
复制标题
搜索带门多边形房间的高效算法
DOI：
10.1007/3-540-47738-1_32
复制
发表时间：
2000
期刊：
影响因子：
--
通讯作者：
X. Tan
中科院分区：
文献类型：
--
作者：
X. Tan
本文研究了在一个有门的多边形房间P中移动的入侵者的搜索问题。其目标是确定是否存在一个检测入侵者而不允许他驱逐通过d的搜索时间表，无论他移动多快，如果是这样，生成一个搜索时间表。如果一个人拿着手电筒，但只能看到手电筒发出的长长的光线，他就被称为“k-搜索者”。如果有人用手电筒照他，他就会被发现。对于1-边值问题，本文给出了一个时间复杂度为O（nlogn+m），空间复杂度为O（n）的最优搜索算法，如果存在的话，其中的顶点数是，Pandm（≤ n2）是清除P所需的最少搜索指令数，这改进了以前的O（n2）时间和空间的限制.我们的算法的最优性是通过识别发生在P中的关键可见性事件，并在此基础上分解搜索时间表来获得的。此外，我们的方法可以很容易地扩展到解决的问题，搜索一个房间的2-搜索引擎。该扩展基于可见性概念到link-2-visibility概念的概括。
We study the problem of searching for a mobile intruder in a polygonal roomPwith a doordby a mobile searcher. The objective is to decide whether there exists asearch scheduleto detect the intruder without allowing him to evict throughd, no matter how fast he moves, and if so, generate a search schedule. A searcher is called thek-searcherif he holdskflashlights and can see only alongkrays emanating from his flashlights. The intruder is detected if he is ever illuminated by a flashlight. For a 1-searcher, we present an optimalO(nlogn+m) time andO(n)space algorithm for generating a search schedule, if it exists, wherenis the number of vertices ofPandm(≤ n2) is the minimum number of search instructions required to clear P. This improves upon the previousO(n2) time and space bounds. The optimality of our algorithm is obtained by identifying critical visibility events occurred inPand decomposing the search schedule based on them. Furthermore, our method can easily be extended to solve the problem of searching a room by a 2-searcher. The extension is based on a generalization of the notion of visibility to that of link-2-visibility.