假设A和B是平面上的两组点，每组都由n个点组成。 我正在尝试找到一种有效的方法来确定是否可以通过一个圆盘将A和B分离 - 是否存在一个圆盘D，使得所有A中的点都在D内，而所有B中的点都在D外？
这里还有一个提示： 使用三维提升。
任何帮助将不胜感激。
1个回答
6
将点嵌入到 (x, y) ↦ (x, y, x² + y²)，并测试是否存在分离超平面。这个方法的原理是：
- 如果我们有参数 (a, b, c)，满足当 (x, y) ∈ A 时 a x + b y + x² + y² < c，当 (x, y) ∈ B 时 a x + b y + x² + y² > c，那么比较等价于 (x − (−a/2))² + (y − (−b/2))² ? c + (−a/2)² + (−b/2)²，这相当于一个以中心为 (−a/2, −b/2)，半径为 √(c + (−a/2)² + (−b/2)²) 的分离圆； - 反之，我们可以通过代数运算从分离圆得到分离超平面。
- 如果我们有参数 (a, b, c)，满足当 (x, y) ∈ A 时 a x + b y + x² + y² < c，当 (x, y) ∈ B 时 a x + b y + x² + y² > c，那么比较等价于 (x − (−a/2))² + (y − (−b/2))² ? c + (−a/2)² + (−b/2)²，这相当于一个以中心为 (−a/2, −b/2)，半径为 √(c + (−a/2)² + (−b/2)²) 的分离圆； - 反之，我们可以通过代数运算从分离圆得到分离超平面。
- David Eisenstat
1
1@firev2 可能需要我更长时间，但将高阶项嵌入额外维度在数学的几个不同分支中都有应用。 - David Eisenstat
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接