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.
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.
