common overlap of N circles

Question

Having N circles represented by their radius and center coordinates , I wanted to know if there exists an algorithm for finding whether or not the point P exists such that P is inside all of the circles.

Answer 1

One simple O(n^3) method is to simply compute the points of intersection for every pair of circles and then for each intersection point test to see if it is in all of the circles.

There will be O(n^2) intersection points, and testing each of these takes O(n), so overall it is O(n^3).

I believe the only way there can be points inside all circles and not an intersection point is if the innermost circle is completely inside the other circles, so you should also test the centre of each circle.

Answer 2

If you could calculate intersections sequentially then you can get O(N^2) algorithm.

Each circles intersection is a convex figure similar to a polygon, but with arc sides. After you intersect n first circles you'll get the intersection area with not more than O(n) sides. So in order to calculate its intersection with the next (n+1-th) circle you'll need O(n) work. Going over all N circles you'll need the O(N^2) work total.

The advantage of this algorithm is also its earlier termination with answer no - if you get an empty intersection on step n it won't become nonempty in following steps.

A disadvantage - a necessity to deal with "arced" polygons.