我想实现一个程序，将平面中的 n 个点的集合 S 分成两组，使两组凸包的距离最大化。
它应该在 O(n^3) 中完成。
我有几个想法，但我不确定它们是否正确：
1. 想法：我按 X 对点进行排序，然后为每两个点找到距离，但前提是它们之间没有任何其他点。然后我选择最接近左边第一个的点和最接近右边第二个的点（第一个点是第一个多边形的一部分，第二个是第二个多边形的一部分）。然后我找到点与线、线与线、线与点、点与点之间的距离（但我已经知道了）。这就是我找到最大距离的方法，然后使用格雷厄姆扫描创建一个凸包。我对 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) 。