Covering convex polygons with inscribed disks

Question

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

Answer 1

Here is a slight variation of the nice algorithm of Yoav.

(1) Pack $P$ with disks with Eppstein's $O(n \log n)$ algorithm (where $n$ is the number of vertices of $P$).

(2) Modify as described in this paper,

Marshall Bern, Erik Demaine, David Eppstein, and Barry Hayes, “A Disk-Packing Algorithm for an Origami Magic Trick”, in Proceedings of the International Conference on Fun with Algorithms (FUN'98), Isola d'Elba, Italy, June 18–20, 1998, pages 32–42. (link here)

so that all gaps are either 3-gaps or 4-gaps, i.e., bounded by three or four arcs, as in the figure below.
        

(3) Proceed as in Yoav's algorithm.

The advantage is that from now on, all gaps are 3- or 4-gaps and are easier to fill than arbitrarily shaped gaps.

One other point. You could stop the filling at some stage above $\epsilon$ coverage, and enlarge the disks keeping their centers fixed, so that they overlap by $\le \delta$. This would reduce the number of disks needed. If you follow this enlarging, you should start with $P$ offset inward to accommodate the later enlarging.

Answer 2

The greedy approach wouldn't be that hard to implement, and doesn't require polygonal approximations.

Just think of $P$ as the space between zero-curvature disks. Then at each step of the algorithm, you have a region bounded by disks, and you want to find the largest disk that is tangent to three boundary disks, and not intersecting any others. After this, you are left with three (generically, possibly more if things are degenerate) regions to add to your stack.

You want to this depth-first, to avoid using too much memory, so you should stop going down a branch if the region has area $<3^{-d} \epsilon$, where $d$ is the depth. Alternatively, stop if the region can be circumscribed by a disk such that the overlap created is $<3^{-d}\delta$.