Abstract. We study the problem of covering a two-dimensional spatial region P , cluttered with occluders, by sensors. A sensor placed at a location p covers a point x in P if x lies within sensing radius r from p and x is visible from p, i.e., the segment px does not intersect any occluder. The goal is to compute a placement of the minimum number of sensors that cover P . We propose a landmark-based approach for covering P . Suppose P has ς holes, and it can be covered by h sensors. Given a small parameter ε > 0, let λ := λ(h, ε) = (h/ε) log ς. We prove that one can compute a set L of O(λ log λ log (1/ε)) landmarks so that if a set S of sensors covers L, then S covers at least (1 − ε)-fraction of P . It is surprising that so few landmarks are needed, and that the number does not depend on the number of vertices in P . We then present efficient randomized algorithms, based on the greedy approach, that, with high probability, compute O(h log λ) sensor locations to cover L; hereh ≤ h is the number sensors needed to cover L. We propose various extensions of our approach, including: (i) a weight function over P is given and S should cover at least (1 − ε) of the weighted area of P , and (ii) each point of P is covered by at least t sensors, for a given parameter t ≥ 1.
Related, Agarwal et al. REF propose a greedy landmarkbased method that solves for the placement of the minimum number of beacons (within a log factor) necessary to cover all but a fraction of a given polygonal environment.
Efficient sensor placement for surveillance problems
DCOSS
Computer Science