我想实现一个程序，将平面上 n 个点的集合 S 分成两组，使得两组凸包的距离最大化。
应该在 O(n^3) 中完成。
我有几个想法，但我不确定它们是否正确:
1. 想法:我按 X 对点进行排序，然后为每两个点找到距离，但前提是它们之间没有任何其他点。然后我选择离左边第一个最近的点和右边第二个最近的点(第一个点是第一个多边形的一部分，第二个点是第二个多边形的一部分)。然后我找到点和线、线和线、线和点以及点和点之间的距离(但我已经知道了)。这就是我找到最大距离然后使用 Graham 扫描创建凸包的方法。
我为 Y 重复所有内容，因为最大距离可能在 Y 上，而不是在 X 上。
2. 想法:我按 X 对点进行排序，然后为前 3 个点创建一个凸包，为其他点创建另一个凸包。然后找到这两个船体之间的最小距离。我保存距离，如果它大于我在覆盖它并记住多边形之前保存的距离。最后一步是当第二个凸包只剩下 3 个点时。然后我为 Y 执行所有这些步骤。
你们觉得我的想法怎么样？您有任何改进或其他更好的想法吗？
最佳答案
O(N^3) 如果你够聪明的话，使用分离轴定理是可能的。先看这个:https://gamedevelopment.tutsplus.com/tutorials/collision-detection-using-the-separating-axis-theorem--gamedev-169
现在，如果两个凸包之间的距离为 x，则存在一个轴，这些凸包中的点沿该轴被 x 分隔。相反，如果沿任何轴的点的投影之间存在 x 的间隙，则该间隙两侧的点的凸包将至少分开 x.
因此，如果您找到点之间具有最大间隙的轴，则该间隙两侧的点组的凸包之间的距离将尽可能大。
好消息是只有 O(N^2) 个可能的最佳轴。两个凸包之间的距离要么是包中两点(角)之间的距离，要么是其中一个点与另一个包中的一条线之间的距离。在第一种情况下，相应的分离轴将沿着任一船体中的点之间的线。在第二种情况下，分离轴将垂直于一个船体中的线。无论哪种方式，轴要么垂直于要么平行于两点之间的线，并且只有 O(N^2) 个这样的方向。
因此，您可以尝试所有可能的方向，沿着每个轴对点进行排序，并找到它们之间的最大差距。总时间是... O(N^3 * log N) 不够好。
为了将其降低到 O(N^2)，您必须将每个轴的排序降低到 O(N)。事实证明，这其实没有问题。如果您按斜率顺序遍历所有可能的轴方向，那么沿途看到的反转总数(改变顺序的点对)为 O(N^2)。如果您使用插入排序对每个轴的点进行求和，那么它将进行的移动总量与它进行的反转次数成正比。这将是 O(N^2) 加在一起。将其与每个方向的线性扫描部分相加得到 O(N^3) 总工作量。
关于java - 最大化两个凸包之间的最小距离，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/51935796/