Department of Mathematics
 Search | Help | Login | pdf version | printable version

Math @ Duke





.......................

.......................


Publications [#235517] of Pankaj K. Agarwal

Papers Published

  1. Agarwal, PK; Ezra, E; Ganjugunte, SK, Efficient sensor placement for surveillance problems, Lecture notes in computer science, vol. 5516 LNCS (2009), pp. 301-314, ISSN 0302-9743 [doi]
    (last updated on 2017/12/15)

    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/ε) (1∈+∈ln (1∈+∈ς)). 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 of landmarks depends only on h, and does not directly depend on the number of vertices in P. We then present efficient randomized algorithms, based on the greedy approach, that, with high probability, compute sensor locations to cover L; here 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. © 2009 Springer Berlin Heidelberg.

 

dept@math.duke.edu
ph: 919.660.2800
fax: 919.660.2821

Mathematics Department
Duke University, Box 90320
Durham, NC 27708-0320