5

I have a set of n given circles. I want to find that if there exists at least one point that lies in all of the given circles. Is there a method to do so? I can definitely find a set of points and then iterate over them, but all I want is to find if a possibility exists, I have no use of the exact point(s).

PS: Circles can be of any radii

Aryabhata
  • 82,206
Amit
  • 151
  • Can the circles be of any radius? If they are all of the same radius $r$, then a necessary and sufficient condition is that all the circles can be contained in a circle of radius $2r$. – Peter Woolfitt Jul 01 '14 at 18:25
  • @PeterWoolfitt Circles can be of any radii – Amit Jul 01 '14 at 18:32
  • this looks like a programming exercise rather than a maths one. – Lost1 Jul 01 '14 at 18:47
  • @Lost1 I am looking for a theorem. Programming would be useful to find the points. I only want to see if a theorem exists to find the plausibility of a solution to exist. – Amit Jul 01 '14 at 18:53
  • 3
    Helly's theorem reduces it to the case $n=3$, which could perhaps be solved directly. –  Jul 01 '14 at 18:55
  • @StevenTaschuk so you are suggesting checking $C^n_3$ sets of circles, interesting. – Lost1 Jul 01 '14 at 18:58
  • @Lost1 So this method as well as Rahul's answer below are bot $O(n^3)$. Can we do any better? Maybe presort the circles in a useful manner? – Hagen von Eitzen Jul 01 '14 at 19:33
  • That's equivalent to finding a solution to the system: $$\left(x-a_i\right)^2+\left(y-b_i\right)^2\leq r_i^2$$ which can be reduced to $n-1$ linear equations and $1$ nonlinear equation. – user5402 Jul 01 '14 at 19:33
  • I meant inequalities not equations. – user5402 Jul 01 '14 at 19:53
  • @HagenvonEitzen I merely commented that Steven's suggestion was interesting and it is something I have not thought about before... – Lost1 Jul 01 '14 at 20:18
  • @HagenvonEitzen: A perhaps interesting example: take three equal-radius circles centred at the vertices of an equilateral triangle, the radius large enough that they intersect pairwise (in particular, at the midpoints of the sides), but small enough that they don't all three have a common point; then add any number of circles which contain all three of the midpoints of the sides. Of the $\binom n3$ triples of circles here, only one fails to have a common point. So... well, it's not a proof that $n^3$ is optimal, but it does mean that I'd be very interested in any sub-$n^3$ algorithm. –  Jul 01 '14 at 21:34
  • @Steven: Please see my updated answer. The algorithm doesn't need to try all $\binom n3$ triples. –  Jul 02 '14 at 00:15
  • @StevenTaschuk: If you are looking for a deterministic sub-cubic algorithm, I believe there might be. If we change our objective to compute the intersection. We might might be able to use divide-and-conquer then. – Aryabhata Jul 02 '14 at 23:56
  • Possible duplicate of Check whether $n$ disks intersect – obsolesced Oct 31 '16 at 05:15

1 Answers1

3

Shamelessly cribbing from my previous answer:

What you are asking is whether the intersection of $n$ disks is nonempty. Said intersection is a convex shape bounded by circular arcs that meet at vertices where two or more circles intersect.

Consider every pair of circles; find their two intersection points, which form two candidate vertices; if a candidate vertex is inside all other circles, then it is indeed a vertex of the intersection. This gives you the set of vertices of the intersection shape.

Then, the intersection is nonempty if and only if: (i) the set of vertices is nonempty, or (ii) there exists a circle that is entirely inside all the others.

As Hagen von Eitzen points out, this not-very-clever algorithm takes $O(n^3)$ time. A much more efficient solution is possible.

Instead of finding just any point in the intersection of the given disks, we'll try to find the leftmost point, that is, the point with the smallest $x$-coordinate. Specifically, for any set of disks $S$, define $f(S)$ to be the smallest $x$-coordinate of all points in the intersection $\bigcap S$, or $+\infty$ if $\bigcap S$ is empty.

Computing $f$ is an LP-type problem because $f$ satisfies the following two properties:

  1. Monotonicity: if $A\subseteq B$ then $f(A)\le f(B)$. This holds because adding more disks can only shrink the intersection and make the smallest $x$-coordinate larger. Formally, $\bigcap B\subseteq\bigcap A$.

  2. Locality: if $A\subseteq B$ and $f(A)=f(B)=f(A\cup\{x\})$, then $f(A)=f(B\cup\{x\})$. This holds because the first equality implies that the leftmost point in $\bigcap A$ lies in $\bigcap B$ and in $x$, and so it also lies in $\bigcap\big(B\cup\{x\}\big)$.

Being an LP-type problem, $f$ can be computed in expected $O(n)$ time by any of several randomized algorithms.

Seeing the analogy to linear programming, I guess this algorithm is like the simplex method while the previous one is like finding all potential vertices of the feasible polytope and testing them.

Community
  • 1
  • 1
    In other words: It suffices to test points in the finite set consisting of all circle intersections together with all circle centers. That's at most $n^2$ points, so $O(n^3)$ in total. – Hagen von Eitzen Jul 01 '14 at 19:27
  • @Hagen: I've added an expected linear time algorithm. –  Jul 02 '14 at 00:14
  • 1
    The algorithms for LP-type problems are indeed interesting. The Wikipedia page doesn't mention the worst case performance, just the expected. Do you know off-hand anything about the worst case? –  Jul 02 '14 at 22:42
  • @Steven: I'm afraid not, but I wouldn't be surprised if it were exponential. –  Jul 02 '14 at 22:53