Find if a point lies in all given circles 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
 A: 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:


*

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

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