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$.