5
$\begingroup$

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

$\endgroup$
3
  • $\begingroup$ Greedy is an interesting problem, leading to Apollonian packings. But as you say, probably not optimal. An alternative, regular lattices of small disks, may not be optimal either. So, good question! Of course, removing any disk (not just greedy) leads to a non-convex non-polytope. $\endgroup$
    – user25199
    Jul 25, 2013 at 21:10
  • $\begingroup$ Maybe starting with a fixed Apollonian gasket and using a conformal map to map the unit disk to $P$ could be an approach which could be made to work? $\endgroup$ Jul 25, 2013 at 23:17
  • $\begingroup$ Better yet probably, start with a fixed Apollonian gasket in a triangle, triangulate $P$, take a conformal map mapping vertices to vertices from the original triangle to the triangles that make up $P$. Presumably this conformal map is common enough that is implemented in some library. $\endgroup$ Jul 26, 2013 at 0:41

2 Answers 2

5
$\begingroup$

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.
        Fig1 Retouched

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

$\endgroup$
2
  • $\begingroup$ Thanks for the answer (and the picture)! Is there a general reason why filling 3 and 4 gaps is easier? One could concoct a long skinny 3-gap which would presumably take more disks to cover than, say, a more regular shape. Also, in the application it is necessary to have the disks completely contained in the polytope (so the boundary disks in your picture would be disallowed). $\endgroup$ Jul 26, 2013 at 1:32
  • 1
    $\begingroup$ That image is taken from Fig.1 of the paper I cited; I just wanted to illustrate the gaps. The computation of one disk to fill such a gap with the largest disk is easy, and then you are left with the same type of gaps for the next iteration. $\endgroup$ Jul 26, 2013 at 1:48
4
$\begingroup$

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

$\endgroup$
4
  • $\begingroup$ Thank you, this looks like a promising idea. Is it efficient to compute these areas at each step when deciding whether the area is bounded? Similarly, I'm not sure how to check effectively that the complement of some disks in a polytope is circumscribable by another disk. $\endgroup$ Jul 26, 2013 at 1:35
  • $\begingroup$ In the generic case, your region will be bounded by three circles (possibly of zero curvature) that are tangent to each other. Calculating the area of this region is easy (think of the triangle formed by the centers minus the three circular sectors). Other cases that arise, but are not much harder: near corners of $P$ you will have a region bounded by two lines and a circle tangent to them; you will unavoidably have some regions bounded by a cycle of four tangent circles. $\endgroup$ Jul 26, 2013 at 2:05
  • $\begingroup$ For the circle circumscribing the region, this is also easy if you think about the three cases above. Obviously, this is not applicable for regions that abut the boundary of $P$. $\endgroup$ Jul 26, 2013 at 2:06
  • $\begingroup$ As for efficiency of calculating this area at each step, it seems it should be too inefficient. If for some reason it is, I can think of many ways of approximating it cheaply. $\endgroup$ Jul 26, 2013 at 2:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.