TY - JOUR

T1 - The searchlight problem for road networks

AU - Dereniowski, Dariusz

AU - Ono, Hirotaka

AU - Suzuki, Ichiro

AU - Wrona, Łukasz

AU - Yamashita, Masafumi

AU - Zyliński, Paweł

N1 - Publisher Copyright:
© 2015 Elsevier B.V.

PY - 2015/8/2

Y1 - 2015/8/2

N2 - 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{2g-1, n-2} searchlights are sometimes necessary and min{73g,n}-1 are always sufficient for searching a road network given as the union of n lines;2.Ω(glog ng) searchlights are sometimes necessary and O(g2logn) searchlights are always sufficient for searching a road network given as the union of n line segments, and3.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.

AB - 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{2g-1, n-2} searchlights are sometimes necessary and min{73g,n}-1 are always sufficient for searching a road network given as the union of n lines;2.Ω(glog ng) searchlights are sometimes necessary and O(g2logn) searchlights are always sufficient for searching a road network given as the union of n line segments, and3.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.

UR - http://www.scopus.com/inward/record.url?scp=84943661181&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84943661181&partnerID=8YFLogxK

U2 - 10.1016/j.tcs.2015.04.026

DO - 10.1016/j.tcs.2015.04.026

M3 - Article

AN - SCOPUS:84943661181

SN - 0304-3975

VL - 591

SP - 28

EP - 59

JO - Theoretical Computer Science

JF - Theoretical Computer Science

ER -