Abstract: We consider a geometric optimization problem that arises in
sensor network design. Given a polygon $P$ (possibly with holes) with
$n$ vertices, a set $Y$ of $m$ points representing sensors, and an integer $k$,
$1 le k le m$. The goal is to assign a sensing range, $r_i$, to each of
the sensors $y_i in Y$, such that each point $p in P$ is covered by
at least $k$ sensors, and the cost, $sum_i r_i^alpha$, of the assignment
is minimized, where $alpha$ is a constant.

Here, we assume that $alpha = 2$, that is, find a set of disks centered
at points of $Y$, such that (i) each point in $P$ is covered by at least
$k$ disks, and (ii) the sum of the areas of the disks is minimized. We present,
for any constant $k ge 1$, a polynomial-time $c_1$-approximation algorithm
for this problem, where $c_1=c_1(k)$ is a constant. The discrete version,
where one has to cover a given set of $n$ points, $X$, by disks centered
at points of $Y$, arises as a subproblem. We present a polynomial-time
$c_2$-approximation algorithm for this problem, where $c_2=c_2(k)$ is
a constant.

Joint work with A. Karim Abu-Affash, Paz Carmi and Matya Katz.