Determine if circle is covered by some set of other circles - MathOverflow most recent 30 from http://mathoverflow.net 2013-06-19T18:38:33Z http://mathoverflow.net/feeds/question/76712 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/76712/determine-if-circle-is-covered-by-some-set-of-other-circles Determine if circle is covered by some set of other circles Adrian Schönig 2011-09-29T00:51:39Z 2011-10-04T23:34:07Z <p>Suppose you have a set of circles $\mathcal{C} = {C_1, .., 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.</p> <p>How can you determine whether the area covered by the $C_{n+1}$ is fully covered by $\mathcal{C}$?</p> <p>How to do this if the circles can have varying radii?</p> <p><strong>Note</strong>: 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_{intersecting}}$ (subset of $\mathcal{C}$ with circles that are within $2r$ of $C_{n+1}$).</p> http://mathoverflow.net/questions/76712/determine-if-circle-is-covered-by-some-set-of-other-circles/76718#76718 Answer by Anton Petrunin for Determine if circle is covered by some set of other circles Anton Petrunin 2011-09-29T01:33:50Z 2011-10-04T23:34:07Z <p>I would try to use <a href="http://en.wikipedia.org/wiki/Voronoi_diagram" rel="nofollow">Voronoi domains</a> $$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</p> <ul> <li>each vertexes $a\in C_{n+1}$ of Voronoi domain $V_i$.</li> <li>and each point of intersection $\partial V_i\cap \partial C_{n+1}$</li> </ul> <p>lies in $C_i$.</p> <p>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 <a href="http://en.wikipedia.org/wiki/Power_of_a_point" rel="nofollow">power of the point</a> $x$ with respect to $C_i$.</p> <p><strong>P.S.</strong> 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 <a href="http://en.wikipedia.org/wiki/Fortune%27s_algorithm" rel="nofollow">see wikipedia</a> and one needs to check check only $O(n)$ points after one makes the diagram. </p> http://mathoverflow.net/questions/76712/determine-if-circle-is-covered-by-some-set-of-other-circles/76719#76719 Answer by jc for Determine if circle is covered by some set of other circles jc 2011-09-29T01:41:52Z 2011-09-29T01:48:26Z <p>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 <a href="http://www.cs.duke.edu/~edels/Publications/Alpha/" rel="nofollow">here</a> 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.</p> <p>The abstract of that paper:</p> <blockquote> <p>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. </p> </blockquote> <p>I think the main idea is basically that suggested by Anton Petrunin.</p> http://mathoverflow.net/questions/76712/determine-if-circle-is-covered-by-some-set-of-other-circles/76720#76720 Answer by Carl Feynman for Determine if circle is covered by some set of other circles Carl Feynman 2011-09-29T02:35:51Z 2011-09-29T02:35:51Z <p>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'. </p> <p>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.</p> http://mathoverflow.net/questions/76712/determine-if-circle-is-covered-by-some-set-of-other-circles/76752#76752 Answer by Joseph O'Rourke for Determine if circle is covered by some set of other circles Joseph O'Rourke 2011-09-29T11:50:38Z 2011-09-29T11:50:38Z <p>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$. <br />&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<img src="http://cs.smith.edu/~orourke/MathOverflow/DiskOverlap.jpg" alt="Disk Overlap"> <br /> 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, <em>Discrete &amp; Computational Geometry</em>, Volume 21, Number 3, 1999, 321-328.</p> http://mathoverflow.net/questions/76712/determine-if-circle-is-covered-by-some-set-of-other-circles/76907#76907 Answer by Aaron Golden for Determine if circle is covered by some set of other circles Aaron Golden 2011-10-01T02:57:06Z 2011-10-01T02:57:06Z <p>This is intended as a comment on Carl Feynman's answer, but I lack the MO reputation to leave comments.</p> <p>I wanted to point out that the recursive subdivision algorithm can be made a little faster, and the infinite recursion problem can be avoided in the following way: As a first step iterate over $C$ and discard any members, $C_j$, where the sum of the radius of $C_j$ and the radius of $C_{n+1}$ is less than or equal to the distance from the center of $C_j$ to the center of $C_{n+1}$. You could also save yourself a few recursions by making the initial rectangle a square bounding only $C_{n+1}$ instead of a rectangle bounding all of the circles.</p> http://mathoverflow.net/questions/76712/determine-if-circle-is-covered-by-some-set-of-other-circles/77020#77020 Answer by Igor Rivin for Determine if circle is covered by some set of other circles Igor Rivin 2011-10-03T07:35:59Z 2011-10-03T07:35:59Z <p>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).</p> http://mathoverflow.net/questions/76712/determine-if-circle-is-covered-by-some-set-of-other-circles/77067#77067 Answer by David Eppstein for Determine if circle is covered by some set of other circles David Eppstein 2011-10-03T18:44:34Z 2011-10-03T23:58:38Z <p>See <a href="http://mathoverflow.net/questions/24859/finding-the-union-of-n-random-circles-arbitrarily-or-conspiratorially-placed-on" rel="nofollow">this earlier MO question</a>. 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.</p> http://mathoverflow.net/questions/76712/determine-if-circle-is-covered-by-some-set-of-other-circles/77075#77075 Answer by Al Tal for Determine if circle is covered by some set of other circles Al Tal 2011-10-03T20:36:26Z 2011-10-03T21:03:16Z <p>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. </p> <p>In the beginning we throw away every $C_i$ ($1\leq i\leq n$) that doesn't intersect $C_{n+1}$. </p> <p>We also throw away every $C_i$ ($1\leq i\leq n$) that lies inside another $C_j$ ($1\leq j\leq n$).</p> <p>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.</p> <p>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$?</p> <p>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 </p> <p>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. </p> <p>If not, we continue and check if $\partial U$ doesn't contain points inside $C_{n+1}$. We do that with</p> <p>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> <p>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$.</p> http://mathoverflow.net/questions/76712/determine-if-circle-is-covered-by-some-set-of-other-circles/77083#77083 Answer by Sergei Ivanov for Determine if circle is covered by some set of other circles Sergei Ivanov 2011-10-03T23:15:11Z 2011-10-03T23:15:11Z <p>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.</p> <p>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.</p> <p>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.</p>