The following problem came up when discussing mapping software (e.g., Google maps) with computer scientists. By $B(c,r)$ I mean the planar disk (open or closed, it doesn't matter) of radius $r$ around the point $c$.

Consider a finite collection of points in the plane whose convex hull we call $P$. Here's the question:

Given $\epsilon, \delta > 0$ and the vertices of $P$, can we efficiently produce a finite collection of balls $B_j = B(c_j,r_j)$ so that (1) each $B_j$ is contained completely in $P$, (2) the area of $P$ not contained in any of the balls is smaller than $\epsilon$, and (3) the area covered by more than one ball is smaller than $\delta$?

Basically, the problem requires an efficient way to cover a convex polytope by inscribed disks so that we simultaneously maximize the covered area and minimize the multiply-covered area. I would be happy with any approach, greedy or otherwise, which achieves such an optimization If this is hopeless, can we make progress by dropping requirement (3) entirely?

Note also that the naive/greedy approach which starts by finding the largest inscribed disk $B_P \subset P$ and focusing attention on $P' = P \setminus B_P$ immediately puts us in an unfriendly setting: $P'$ is neither convex nor a polytope. I can't see how to make a greedy recursive approach work without essentially constructing a polygonal approximation of $B_P$.