The searchlight problem for road networks
The searchlight problem for road networks
复制标题
道路网络的探照灯问题
DOI：
10.1016/j.tcs.2015.04.026
复制
发表时间：
2015
影响因子：
1.1
通讯作者：
Pawel Zylinski
中科院分区：
文献类型：
--
作者：
Dariusz Dereniowski;Hirotaka Ono;Ichiro Suzuki;Lukasz Wrona;Masafumi Yamashita;Pawel Zylinski
我们考虑搜索隐藏在平面上的两条或多条线或两条或多条线段的路网中的移动入侵者的问题。道路网的一些十字路口被配备了探照灯的固定警卫占据，每一个探照灯都可以沿着它所在的线（或线段）向任何方向发射一束光。目标是检测入侵者，也就是说，确定其位置。警卫可以改变他们瞄准探照灯的方向，但需要在一段有限的时间间隔内关闭探照灯以影响改变。相比之下，入侵者可能以任意速度沿着网络移动（但不能通过警卫），并利用这段时间间隔重新污染先前被照亮的网络部分。对于由n条线（或线段）组成的各种类型的道路网络，以及g（≤n−1）个可能的警卫位置（预先固定并保证完全覆盖），我们提出了几个最坏情况下探照灯数量的上限和下限，每个探照灯放置在一个警卫位置，需要成功搜索给定的道路网络。特别地，我们证明了以下结果：1。对于n条线并集的路网，有时需要Min （2 g−1,n−2）探照灯，而Min （7 3 g, n}−1）探照灯总是足够的；2. Ω （g⋅log (n) g）探照灯有时是必要的，O （g 2⋅log (n)）探照灯对于搜索给定为n条线段和3的路网总是足够的。每个警戒位置最多有一个探照灯，因此总共最多有g个探照灯，对于搜索作为轴线对齐的线或线段的并集的路网总是足够的。上界的证明推导出用于生成搜索调度的算法，该搜索调度用于使用所要求的探照灯数量来检测入侵者。
We consider the problem of searching for a mobile intruder hiding in a road network given as the union of two or more lines, or two or more line segments, in the plane. Some of the intersections of the road network are occupied by stationary guards equipped with a number of searchlights, each of which can emit a single ray of light in any direction along the lines (or line segments) it is on. The goal is to detect the intruder, that is, to illuminate its location. Guards may alter the direction in which they aim a searchlight, but need to switch it off for some finite time interval to effect the change. In contrast, the intruder may move with arbitrary speed along the network (but cannot pass guards) and exploit this time interval to recontaminate previously illuminated sections of the network. For various classes of road networks characterized by the number n of lines (or line segments) comprising it and the number g (≤ n− 1) of possible locations of guards (fixed in advance and guaranteed to give complete coverage), we present several upper and lower bounds on the worst-case number of searchlights, each placed at one of the guard positions, required to successfully search a given road network. In particular, we prove the following results: 1. min{2 g− 1, n− 2} searchlights are sometimes necessary and min{7 3 g, n}− 1 are always sufficient for searching a road network given as the union of n lines; 2. Ω (g⋅ log n g) searchlights are sometimes necessary and O (g 2⋅ log n) searchlights are always sufficient for searching a road network given as the union of n line segments, and 3. at most one searchlight per guard position, and hence a total of at most g searchlights, is always sufficient for searching a road network given as the union of axis-aligned lines or line segments. The proofs of the upper bounds induce algorithms for generating a search schedule for detecting the intruder using the claimed number of searchlights.