How do you determine if you can draw a circle around a set of points, such that the points from the other set aren't inside it?

Question

I am wondering about an algorithm that returns true or false, telling me if it's possible to draw a circle around a set of points A, such that any point from the set of points B is not inside it, or the other way around (possible to draw a circle around a set of points B, such that any point from the set of points A is not inside it).

Basically, you are given 2 sets of points as input, and you need to determine if it's possible to draw a circle around either one, such that any point from the other isn't inside it.

I have looked at Megiddo's linear time algorithm for the smallest enclosing circle problem, but the problem is that it only draws the smallest circle, which means it doesn't work in the case where you need a large circle.

Here's a pic of what I mean:

In this picture it's possible to draw a very large circle around the set of red points, so that any one of the green points aren't inside it, hence Megiddo's algorithm won't work.

Answer 1

Try this: use stereographic projection to project your points onto a sphere. Then you need to find a plane passing through the sphere that cuts the sphere so that all points in the first set are on one side of the plane, and all points in the second set are on the other side of the plane. The intersection of the plane and the sphere is a circle, which maps back to a circle (or under rare circumstances, a line) on the original plane. The resulting circle on the original plane has the properties you desire.

Changing the problem from one about circles on the plane to one about planes in three dimensions (linear objects) means that you can use ideas from linear programming and convex sets to help. One approach is to use the hyperplane separation theorem to show that you can find a plane that separates the images of the families of points if and only if the convex hulls of the images of points in A and B don't intersect.

There are many fast methods in hardware and software for determining whether two convex bodies intersect: it is the problem of collision detection, important in video games for example. A lot of work has been done on that problem (see, e.g., https://www.medien.ifi.lmu.de/lehre/ss10/ps/Ausarbeitung_Beispiel.pdf, which claims that the algorithm runs in O(n) time) and there is surely freely available code.

In summary: map your points (X,Y) onto the unit sphere (x,y,z) via stereographic projection given by the formula

(x,y,z) = (2*X/(R^2+1), 2*Y/(R^2+1), (R^2-1)/(R^2+1)), R^2 = X^2+Y^2

Then use the Gilbert-Johnson-Keerthi algorithm or some other collision detection algorithm to determine whether the convex hull of the images of points in one set is disjoint from the convex hull of the images of points in the other set. That answers the question of whether the circle exists. To actually find the circle, you need a separating plane between the two convex bodies, which you then intersect with the sphere to obtain a circle on the sphere, which you map back to the plane by the inverse of the stereographic projection.

If I understand correctly, the above can be accomplished in O(n) time.

Answer 2

Just an idea: take all pairs of red and green dots.

For each pair, calculate the orthogonal center line.

These points on the line are the points, where the distance to the green and red dot is equal, so a circle with this as center would not make sense.

But the area on the same side of the line where the red point is also the area, where a potential center point would lie.

For each pair {red,green}, you will get a line and an area, where the center point of the circle would be.

If you intersect all the areas of all the pairs, you will get all potential center points for all circles.

In your example take the two green and the red dot between them. You will get two lines at 1/2 the distance left and right of the vertical axis.

Take the left green dot and all red ones, you will get lines from top left to bottom right and the circle center will be above them.

The right green dot with the red ones will do about the same. So in this case you get a result area (polygon) that is not too far from the vertical axis and at least a certain distance above the horizontal axis and stretches to infinity.

For another set of points the intersection could lead to an empty set, meaning that you cannot draw such a circle around the red ones without taking some of the green ones in.

This will always calculate the correct result, but I have no idea, how good the performance is compared to Joseph's algorithm. Maybe he can take a look?

Answer 3

In this paper, we reduce detecting whether or not two sets of points in the plane can be separated by a circle, to linear separability of points in 3D:

O'Rourke, Joseph, S. Rao Kosaraju, and Nimrod Megiddo. "Computing circular separability." Discrete & Computational Geometry, 1.1 (1986): 105-113. (PDF download.)

Answer 4

If you would test a lot of potential center points (for example on a grid), then for each point the largest distance to any red point would have to be smaller than the smallest distance to any green point, in order to have a circle that contains only red points and no green point.

I guess that by starting with a sparse grid and monitoring the "largest distance to any red point", "smallest distance to any green point" values you can make some promising areas finer and finer (clever sectioning) to finally catch a point or an area with the desired property.

You might even be able to use some derivatives, like going into the direction where the ratio of "largest distance to any red point" to "smallest distance to any green point" decreases most quickly. On the other hand the problem might be non-convex and convergence may not be guaranteed.