Algorithm to determine if a collection of unit discs covers the unit disc centered at the origin?

Question

I have a list of points $ (x_i, y_i) $ for $i = 1...n$. Is there an algorithm to determine if the union of the unit discs centered at these points is a superset of the unit disc centered at $(0, 0)$?

Informally, I'm about to draw a whole bunch of non-transparent filled circles and want to know if I really need to bother drawing all of them. Some of them may be covered by circles that I will draw later. All the circles are the same size so I can do some simple preprocessing to give them all radius 1 and I can move them around so that the circle that I might not need to draw is at $(0, 0)$.

To phrase it a different way, I have a list of quadratic inequalities of the form: $$ \begin{aligned} x^2 + y^2 \leq 1 \\ (x - x_1)^2 + (y - y_1)^2 \geq 1 \\ (x - x_2)^2 + (y - y_2)^2 \geq 1 \\ (x - x_3)^2 + (y - y_3)^2 \geq 1 \\ ... \end{aligned} $$ and need to determine if there is a point that satisfies all of them.

Answer 1

Suppose that the unit discs ("given discs") intersect the unit disc at the origin ("origin disc") but do not cover it completely (we can ignore given discs that do not intersect the origin disc at all). Therefore there must be a point in the origin disc which is on the boundary of a given disc but not covered by the interior of any other given disc (proof: pick an uncovered point, and consider the closest given disc). This reduces our goal to checking, for each given disc $D$, whether all points in the intersection $B$ of its boundary with the origin disc are covered by some given disc.

For any disc $D' \neq D$, one can compute the intersection of $B$ and $D'$ since through computing various intersections of $D$, $D'$ and the origin disc. Furthermore, one can parametrize $B$ as an interval $[0,1]$, and present $B \cap D'$ as a closed subinterval of $[0,1]$.

The question is therefore reduced to determining whether some subintervals of $[0,1]$ cover it. Sort the intervals and the check that adjacent intervals are overlapping, and that both endpoints are covered (I haven't flashed out the details, but probably an algorithm can be constructed along these lines).

Implementing this method efficiently can be tricky, and I don't think that in practice you'll save time this way.

Answer 2

The following algorithm works, although it may be a bit more complicated than what you are looking for:

1. Compute the Voronoi diagram corresponding to the points $(x_i,y_i)$. There is a well-known algorithm for this that runs in $n \log n$ time. See the Wikipedia article on Delaunay triangulations.

2. Let $S$ be the set of vertices of the Voronoi diagram that lie in the disc $x^2 + y^2 \leq 1$, and let $S'$ be the be the set of points on the circle $x^2+y^2=1$ that lie on an edge of the Voronoi diagram.

3. Then the given discs cover the disc $x^2+ y^2 \leq 1$ if and only if the given discs cover the points in $S\cup S'$.

Answer 3

Let $p_i = (x_i, y_i)$, with $p_0 = (0,0)$. For each $i$ and $j$ with $0 \le i < j \le n$, examine the (at most 2) points $q$ with $|p_i - q| = |p_j - q| = 1$. In order for $q$ to be a boundary point of the region $\{p: |p - p_0| \le 1, |p - p_i| > 1\ {\rm for}\ i \ge 1\}$, we need $|q - p_0| \le 1$, $|q - p_k| \ge 1$ for all $k \ge 1$, and there must be a nonzero vector $v$ such that $(q - p_i) . v \ge 0$ for all $i> 0$ for which $|q - p_i| = 1$, while $(q - p_0) . v < 0$ if $|q - p_0| = 1$. Linear programming can be used to decide whether such a vector exists.