设A和B为平面上的两组点——判断A和B能否被圆盘隔开
Let A and B be two sets of points in the plane - determine whether A and B can be separated by a disk
设A和B为平面上的两组点，每组由n个点组成。
我试图找到一种有效的方法来确定 A 和 B 是否可以被一个圆盘分开——是否存在一个圆盘 D，使得 A 的所有点都位于 D 内，而 B 的所有点都位于 D 的一侧？
还有一个提示：
使用提升到三个维度。
如有任何帮助，我们将不胜感激。
将点嵌入为 (x, y) ↦ (x, y, x² + y²) 并测试是否存在分离超平面。这是有效的，因为
如果我们有参数 (a, b, c) 使得 a x + b y + x² + y² < c if (x, y) ∈ A and > c if (x, y) ∈ B，则比较等价于 (x − (−a/2))² + (y − (−b/2))² ? c + (−a/2)² + (−b/2)²，相当于一个以(−a/2, −b/2)为中心，半径为√( c + (−a/2)² + (−b/2)²);
反过来，我们可以做代数从分离圆到分离超平面
设A和B为平面上的两组点，每组由n个点组成。 我试图找到一种有效的方法来确定 A 和 B 是否可以被一个圆盘分开——是否存在一个圆盘 D，使得 A 的所有点都位于 D 内，而 B 的所有点都位于 D 的一侧？
还有一个提示： 使用提升到三个维度。
如有任何帮助，我们将不胜感激。
将点嵌入为 (x, y) ↦ (x, y, x² + y²) 并测试是否存在分离超平面。这是有效的，因为
如果我们有参数 (a, b, c) 使得 a x + b y + x² + y² < c if (x, y) ∈ A and > c if (x, y) ∈ B，则比较等价于 (x − (−a/2))² + (y − (−b/2))² ? c + (−a/2)² + (−b/2)²，相当于一个以(−a/2, −b/2)为中心，半径为√( c + (−a/2)² + (−b/2)²);
反过来，我们可以做代数从分离圆到分离超平面