Let A and B be two sets of points in the plane - determine whether A and B can be separated by a disk

Question

Let A and B be two sets of points in the plane, each consisting of n points. I am trying to find a efficient way to determine whether A and B can be separated by a disk - does there exist a disk D such that all the points of A lie inside D, and all the points of B lie out side it D?

There is also a hint: Use lifting to three dimensions.

Any help will be appreciated.

Answer 1

Embed the points as (x, y) ↦ (x, y, x² + y²) and test whether there is a separating hyperplane. This works because

• If we have parameters (a, b, c) such that a x + b y + x² + y² < c if (x, y) ∈ A and > c if (x, y) ∈ B, then the comparison is equivalent to (x − (−a/2))² + (y − (−b/2))² ? c + (−a/2)² + (−b/2)², which is equivalent to a separating circle with center (−a/2, −b/2) and radius √(c + (−a/2)² + (−b/2)²);

• Conversely, we can do the algebra to go from a separating circle to a separating hyperplane.