algorithm - 设A和B为平面上的两组点——判断A和B能否被圆盘隔开

Question

设A和B是平面上的两组点，每组由n个点组成。我试图找到一种有效的方法来确定 A 和 B 是否可以被一个圆盘分开——是否存在一个圆盘 D，使得 A 的所有点都位于 D 内，而 B 的所有点都位于 D 的一侧？

还有一个提示:使用提升到三个维度。

我们将不胜感激。

Answer 1

将点嵌入为 (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)²);

• 相反，我们可以通过代数计算从分离圆到分离超平面。