Efficient Sensor Placement for Surveillance Problems

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

$O(\tilde{h}\log \lambda)$

sensor locations to cover

L

; here

$\tilde{h} \le 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.