Determine if circle is covered by some set of other circles

Question

Suppose you have a set of circles $\mathcal{C} = \{ C_1, \ldots, C_n \}$ each with a fixed radius $r$ but varying centre coordinates. Next, you are given a new circle $C_{n+1}$ with the same radius $r$ as the previous circles but with a new centre coordinate.

How can you determine whether the area covered by the $C_{n+1}$ is fully covered by $\mathcal{C}$?

How to do this if the circles can have varying radii?

Note: I couldn't yet work out a nice mathematical solution for this. Coming from computer science, the best I could come up with is solving this in a nasty brute force way using some sort of Monte Carlo sampling, i.e. draw a large number of random points from the area of $C_{n+1}$ and then checking for each point if it is enclosed by at least one circle in $\mathcal{C}_{\text{intersecting}}$ (subset of $\mathcal{C}$ with circles that are within $2r$ of $C_{n+1}$).

Answer 1

See this earlier MO question. The union of n disks (represented in terms of its boundary arcs) can be constructed in $O(n\log n)$ time. So construct the union of the $n$ disks you are given, and separately construct the union of the $n+1$ disks including the one you want covered. The given disk is covered if and only if the two unions are the same.

Answer 2

If $n$ is not too large (say, less than $10^4$), and I were faced with actually implementing the computation, I might choose this simple $O(n^2)$ algorithm. Let $R_i$ be the region covered by the target disk (bounded by $C_{n+1}$) minus the disks bounded by $C_1,C_2,\ldots,C_i$. $R_i$ is a collection of regions bounded by circle arcs. It would not be difficult to implement the generic step of subtracting the disk bounded by $C_{i+1}$ from the regions in $R_i$, by intersecting $C_{i+1}$ with each arc comprising the boundary of $R_i$.
     
The reason this algorithm is quadratic is that $\partial R_i$ is $O(n)$. This is not obvious, but established in a paper by János Pach and Micha Sharir, "On the Boundary of the Union of Planar Convex Sets," Discrete & Computational Geometry, Volume 21, Number 3, 1999, 321-328. (Journal link.)

Answer 3

This can be done using a recursive subdivision of the plane by non-overlapping squares. Start with a square big enough to include all the circles. Then one can divide this into four squares of half the edge-length, divide each of those into four, and so on. If we keep track of which squares are inside which next-bigger squares, we end up with a data structure called a quadtree. We're going to recursively construct a quadtree until we either find a square that is entirely inside $C_{n+1}$ and entirely outside all the other circles, or we find a set of squares that cover $C_{n+1}$ and are inside one or more of the other circles. For a given square and a given circle, it's a matter of high-school geometry to decide if the square is entirely inside the circle, entirely outside it, or on the boundary. For each square we compare it against all of the circles, and recurse as follows: if it is entirely within $C_{n+1}$, and entirely outside all the other circles, we return 'false'. Otherwise, if the square is either entirely inside $C$ or entirely outside $C_{n+1}$, it is of no further interest and we discard it. Otherwise, recurse by subdividing the square. If we end up having discarded all squares, return 'true'.

This algorithm can result in infinite recursion if the boundary of $C$ and $C_{n+1}$ coincide at any point. Either be an applied mathematician and cut the recursion off at some sufficiently tiny scale, or be a pure mathematician and use some algebraic geometry to figure out what's happening at the singularity.

Answer 4

I would try to use Voronoi domains $$V_i=\{\,x\in\mathbb R^2\mid |o_i-x|\le |o_j-x|^2\ \text{for all}\ j\,\},$$ where $o_i$ is the center of $C_i$. I guess there are some algorithms which produce it. Then you only need to check that

• each vertexes $a\in C_{n+1}$ of Voronoi domain $V_i$.
• and each point of intersection $\partial V_i\cap \partial C_{n+1}$

lies in $C_i$.

In the case of varying radii, you can still use modified Voronoi domains; $$V_i=\{\,x\in\mathbb R^2\mid f_i(x)\le f_j(x)\ \text{for all}\ j\,\}.$$ where $f_i(x)$ is the power of the point $x$ with respect to $C_i$.

P.S. I deleted my answer earlier sinse I miscalculated time; I thought it takes forever. But Alexander Griffing noticed that, it is $O(n{\cdot} \log n)$ --- $O(n{\cdot} \log n)$ a Voronoi diagram see wikipedia and one needs to check check only $O(n)$ points after one makes the diagram.

Answer 5

The problem (for discs of arbitrary radii) is essentially equivalent to the following: given a convex polyhedral set in $\mathbb R^3$ (represented by a system of linear inequalities), determine whether it intersects the sphere $x^2+y^2+z^2=1$. To solve this, one can check if the set is compact and enumerate its vertices to see whether it lies inside the sphere, and minimize $x^2+y^2+z^2$ over the set to find out whether it is completely outside. I am not an expert in complexity but I believe that the former can be done in $O(n^2)$ time and the latter is even faster.

The reduction goes as follows. Construct a stereographic projection from the plane to the sphere in such a way that the main disc $C_{n+1}$ is mapped to the upper hemisphere. Every other disc is mapped to spherical cap which can be represented as the set of solution of a linear inequality (whose coefficients are easy to compute) intersected with the sphere. Add the inequality $z\le 0$ for the lower hemisphere. Now we need to find out whether the union of corresponding half-spaces cover the sphere. Or, equivalently, whether the intersection of their complement half-spaces have an empty intersection with the sphere. Q.E.D.

The fact that the spherical caps arise from discs in the plane (i.e., not from complements of discs) means that the complement half-spaces except the last one contain the south pole $(0,0,-1)$. However this does not help much. If the original radii are equal, then the complement half-spaces also contain the center $(0,0,0)$. This rules out the case when the intersection is outside the sphere and thus simplifies the problem a little bit.

Answer 6

I believe Herbert Edelsbrunner's work on alpha shapes may have some relevance, though when I was reading about it I was mainly interested in applications to determining volume and surface areas so I'm not sure if the precise question you are asking is addressed. See the papers here on his website, perhaps starting with the paper: H. Edelsbrunner. The union of balls and its dual shape. Discrete Comput. Geom. 13 (1995), 415-440.

The abstract of that paper:

Efficient algorithms are described for computing topological, combinatorial, and metric properties of the union of finitely many spherical balls in $\mathbb{R}^d$ . These algorithms are based on a simplicial complex dual to a decomposition of the union of balls using Voronoi cells, and on short inclusion-exclusion formulas derived from this complex. The algorithms are most relevant in $\mathbb{R}^3$ where unions of finitely many balls are commonly used as models of molecules.

I think the main idea is basically that suggested by Anton Petrunin.

Answer 7

Your question seems equivalent to constructing an ``additively weighed Voronoi diagram'' or ''Apollonian diagram''. You can google either, but the fundamental paper is the one of Franz Aurenhammer (Voronoi Diagrams — A Survey of a Fundamental Geometric Data Structure is a good place to look). The thing can be constructed in poly time, and lookups should be logarithmic (though I am not 100% certain).

Answer 8

Here is a "pretty vanilla" mathematical solution to your problem, which works in $n^3$ time, but programming it is quite easy, it's a matter of 1 hour.

In the beginning we throw away every $C_i$ ($1\leq i\leq n$) that doesn't intersect $C_{n+1}$.

We also throw away every $C_i$ ($1\leq i\leq n$) that lies inside another $C_j$ ($1\leq j\leq n$).

From now on we consider "lunar shades" $L_{i}=C_{n+1} \cap C_{i}$, where $1\leq j\leq n$. Some $L_i$ may remain equal to whole $C_i$, of course.

The initial problem is then equivalent to the following: is $C_{n+1}$ equal to the union $U=\cup_{i=1,\ldots, n} L_i$?

We will reformulate it in this way: is the boundary $\partial U$ equal to the boundary circle $\partial C_{n+1}$. To check this we do the

Check 0) We check the outer border $\partial C_{n+1}$). To do that we find all points $p_j$ which $\partial C_i$ ($1\leq j\leq n$) cut on $\partial C_{n+1}$. Then we sort all these points on theri angle coordinate on $\partial C_{n+1}$, obtaining sorted points $t_j$ ($j=1,\ldots,K\leqslant 2n$). And then for every $j=1,...,K$ we check the middle of the segment $[t_j,t_{j+1}]$ -- whether it belongs to some circle $C_i$ with $1\leq i\leq n$. Of course, we also check the middle point of $[t_K,t_1]$. If some middle points fails, then we are done, and this point is not covered.

If not, we continue and check if $\partial U$ doesn't contain points inside $C_{n+1}$. We do that with

Checks 1...n ) They exactly similar to the Check 0, but we consider the arc $A_j$ of $C_j$ which is inside $C_{n+1}$ as the segment of check. So we again find the points which $C_i$ sect on $C_j$ within $A_j$, including additionally the ends of $A_i$. Then we sort these points up to $C_j$'s angle coordinate and check the middle points -- whether each of them is covered by some circle. If one of these checks fails, we find uncovered points. If all such checks succeed -- then $C_{n+1}$ is covered.

P.S. Using the simple algorithm $n \log n$ for computing the union of segments on a border of circle, one can reduce the complexity to $n^2 \log n$.