A unified and efficient solution to the room search problem
A unified and efficient solution to the room search problem
复制标题
DOI：
10.1016/j.comgeo.2007.04.001
复制
发表时间：
2008-05
期刊：
影响因子：
--
通讯作者：
X. Tan
中科院分区：
文献类型：
--
作者：
X. Tan
研究了移动的入侵者在有门的多边形区域P（称为房间）中搜索的问题。其目标是确定是否存在一个搜索时间表，以检测入侵者，而不允许他退出P通过d，无论他移动多快，如果是这样，生成一个搜索时间表。如果一个人拿着k个手电筒，并且只能看到从他的位置发出的沿着手电筒的光线，那么他就被称为k个人，或者如果1个人的手电筒的两个端点在多边形边界上连续移动，那么他就被称为两个警卫。在本文中，我们开发了一个简单的，统一的解决方案的房间搜索问题。给出了k-可搜索房间和两守卫可步行房间的组成部分和死锁的刻画。通过对非冗余部件和死锁结构的研究，给出了任意搜索调度中出现的临界可见性事件，以及搜索调度结束的P的一个顶点。我们的刻画不仅简单，而且导致所有的决策问题和调度报告问题的有效算法。特别是，我们提出了用于确定房间的1-可搜索性和两名警卫可步行性的最佳O（n）时间算法，以及用于生成搜索计划（如果存在）的O（nlogn+m）时间和O（n）空间算法，其中n是P的顶点数，m（n2）是报告的搜索指令数。
We study the problem of searching for a mobile intruder in a polygonal region P with a door d (called a room) by a mobile searcher. The objective is to decide whether there exists a search schedule for the searcher to detect the intruder without allowing him to exit P through d, no matter how fast he moves, and if so, generate a search schedule. A searcher is called the k-searcher if he holds k flashlights and can see only along the rays of the flashlights emanating from his position, or two guards if two endpoints of the 1-searcher's flashlight move on the polygon boundary continuously. In this paper, we develop a simple, unified solution to the room search problem. The characterizations of the k-searchable and two-guard walkable rooms are all given in terms of components and deadlocks. A study on the structure of non-redundant components and deadlocks gives critical visibility events which occur in any search schedule, and a vertex of P at which our search schedule ends. Our characterizations are not only simple but also lead to efficient algorithms for all decision problems and schedule reporting problems. Particularly, we present optimal O(n) time algorithms for determining the 1-searchability and the two-guard walkability of a room, and an O(nlogn+m) time and O(n) space algorithm for generating a search schedule, if it exists, where n is the number of vertices of P and m(⩽n2) is the number of search instructions reported.