CODEWITHSUNDEEP
algorithmmathgeometrycomputer-sciencecomputational-geometry
ColonelMo
ColonelMo

Reputation: 134

common overlap of N circles

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.

Upvotes: 5

Views: 3444

Answers (3)

fang
fang

Reputation: 3633

Let's see if O(N) algorithm is possible:

1) Find out the circle with smallest radius. Denote it as Cs.
2) Check if Cs is completely enclosed by all other circles. If yes, any point within Cs is the solution. If no, ignore those circles that completely enclose Cs. This will reduce the number of circles to M, where M <= N.
3) Check if any circle intersects Cs. If no circle intersects Cs, there is no solution. If yes, find if any of the intersection points is within all the rest of (M-1) circles. If yes, the intersection point is the solution. If no again, then no solution.

All the above steps are O(N) for computation, so the overall computation should be O(N) as well.

Upvotes: 0

HEKTO
HEKTO

Reputation: 4191

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.

Upvotes: 3

Peter de Rivaz
Peter de Rivaz

Reputation: 33519

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.

Upvotes: 4

Related Questions