The Searchlight Scheduling Problem
The Searchlight Scheduling Problem
复制标题
探照灯调度问题
DOI：
10.1137/0219070
复制
发表时间：
1990
期刊：
影响因子：
--
通讯作者：
M. Yamashita
中科院分区：
文献类型：
--
作者：
K. Sugihara;I. Suzuki;M. Yamashita
研究了多个探照灯在简单多边形内搜索一个移动的劫匪的问题。探照灯是一个固定的点，它发出的单一光线不能穿透多边形的边界。光线的方向可以连续变化，当且仅当一个点在光线上时，探照灯才能在给定的时间内探测到该点。强盗是一个可以以无限速度连续移动的点。首先，它示出的问题，获得一个搜索时间表的实例具有至少一个探照灯的多边形边界上，可以减少到没有探照灯的多边形边界上的实例。通过称为单向扫描策略的递归搜索策略来实现减少。然后利用探照灯可见度图的概念给出了搜索时间表存在的各种充分条件。最后，一个简单的必要和充分条件存在的搜索时间表的实例正好有两个海…
The problem of searching for a mobile robber in a simple polygon by a number of searchlights is considered. A searchlight is a stationary point which emits a single ray that cannot penetrate the boundary of the polygon. The direction of the ray can be changed continuously, and a point is detected by a searchlight at a given time if and only if it is on the ray. A robber is a point that can move continuously with unbounded speed. First, it is shown that the problem of obtaining a search schedule for an instance having at least one searchlight on the polygon boundary can be reduced to that for instances having no searchlight on the polygon boundary. The reduction is achieved by a recursive search strategy called the one-way sweep strategy. Then various sufficient conditions for the existence of a search schedule are presented by using the concept of a searchlight visibility graph. Finally, a simple necessary and sufficient condition for the existence of a search schedule for instances having exactly two sea...