CODEWITHSUNDEEP
algorithmgeometry
ValeraGrinenko
ValeraGrinenko

Reputation: 131

Find point covered by all given circles

Given is n (n <= 1000) circles ((x;y), r) where (x;y) = coordinates of circle center, r = radius. x, y, r <= 10^6. x, y, r, can be real numbers.

The problem is to find point(x;y) covered by all circles, or determine that there are no such points. Coordinates of point can be real numbers too.

No ideas how to do it, could anyone help, please?

Upvotes: 3

Views: 176

Answers (1)

David Eisenstat
David Eisenstat

Reputation: 65427

Assuming that by circle you mean what mathematicians would call a closed disk, there's an O(n²)-time algorithm with simple data structures.

For k from 1 to n, the algorithm finds a point in the intersection of the first k disks, assuming that such a point exists. Start with the center of the first disk. For each disk after the first, check whether the current point belongs to that disk. If so, great. If not, then either the intersection is empty or the intersection contains a point on the boundary of the current disk (the line segment from the current point to any point in the intersection of all of the disks must cross the boundary). In this case, find a new point by intersecting the boundary (a circle) with each of the previous disks, an easier 1D problem.

This might go even faster in expectation if we randomize the order of the disks, but I haven't worked out a proof. With n ≤ 1000, hopefully O(n²) is fast enough.

Sharir ("Intersection and Closest-Pair Problems for a Set of Planar Discs", 1985) may have given an O(n log² n)-time algorithm, but I can't tell from the abstract.

Upvotes: 2

Related Questions