The searchlight problem for road networks

Dariusz Dereniowski, Hirotaka Ono, Ichiro Suzuki, Łukasz Wrona, Masafumi Yamashita, Paweł Zyliński

Research output: Contribution to journalArticlepeer-review

1 Citation (Scopus)


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, 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.

Original languageEnglish
Pages (from-to)28-59
Number of pages32
JournalTheoretical Computer Science
Publication statusPublished - Aug 2 2015

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Computer Science(all)


Dive into the research topics of 'The searchlight problem for road networks'. Together they form a unique fingerprint.

Cite this