The searchlight problem for road networks - Publikacja - MOST Wiedzy

Wyszukiwarka

The searchlight problem for road networks

Abstrakt

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⁡{7g/3,n}-1 are always sufficient for searching a road network given as the union of n lines; 2. Omega(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.

Cytowania

  • 0

    CrossRef

  • 0

    Web of Science

  • 0

    Scopus

Pełna treść

pełna treść publikacji nie jest dostępna w portalu

Informacje szczegółowe

Kategoria:
Publikacja w czasopiśmie
Typ:
artykuł w czasopiśmie wyróżnionym w JCR
Opublikowano w:
THEORETICAL COMPUTER SCIENCE nr 591, strony 28 - 59,
ISSN: 0304-3975
Język:
angielski
Rok wydania:
2015
Opis bibliograficzny:
Dereniowski D., Ono H., Suzuki I., Wrona Ł., Yamashita M., Żyliński P.: The searchlight problem for road networks// THEORETICAL COMPUTER SCIENCE. -Vol. 591, (2015), s.28-59
DOI:
Cyfrowy identyfikator dokumentu elektronicznego (otwiera się w nowej karcie) 10.1016/j.tcs.2015.04.026
Weryfikacja:
Politechnika Gdańska

wyświetlono 19 razy

Publikacje, które mogą cię zainteresować

Meta Tagi