fir*_*ev2 3 algorithm geometry computational-geometry
设 A 和 B 为平面上的两组点，每组由 n 个点组成。我试图找到一种有效的方法来确定 A 和 B 是否可以被圆盘分开 - 是否存在圆盘 D，使得 A 的所有点都位于 D 内部，而 B 的所有点都位于 D 之外？
还有一个提示：使用提升到三个维度。
任何帮助将不胜感激。
将点嵌入为 (x, y) \xe2\x86\xa6 (x, y, x\xc2\xb2 + y\xc2\xb2) 并测试是否存在分离超平面。这有效是因为
\n如果我们有参数 (a, b, c) 使得 ax + by + x\xc2\xb2 + y\xc2\xb2 < c if (x, y) \xe2\x88\x88 A and > c if (x, y) \xe2\x88\x88 B，则比较相当于 (x \xe2\x88\x92 (\xe2\x88\x92a/2))\xc2\xb2 + (y \xe2\x88\x92 (\ xe2\x88\x92b/2))\xc2\xb2 ？c + (\xe2\x88\x92a/2)\xc2\xb2 + (\xe2\x88\x92b/2)\xc2\xb2，相当于以 (\xe2\x88\x92a/2 , \xe2\x88\x92b/2) 和半径 \xe2\x88\x9a(c + (\xe2\x88\x92a/2)\xc2\xb2 + (\xe2\x88\x92b/2)\xc2\xb2 ）；
\n相反，我们可以通过代数从分离圆到分离超平面。
\n