我们知道找到 2 个最近点的快速算法是使用分而治之。 解决方案在这里 http://en.wikipedia.org/wiki/Closest_pair_of_points_problem
现在这里是这个问题的升级版。对于任意三个点 pi, pj , 和 pk, 这些点的三距离 td(p1, p2, p3) 是两个较小的点之和 dist(p1,p2)、dist(p2,p3) 和 dist(p1,p3) 之间的距离。
找出平面上所有可能的 3 点组合的最小三距离的有效方法是什么？
最佳答案
回顾一下最近对的分而治之算法:将 n 个点垂直平分为 n/2 和 n/2。在每一半中找到最接近的一对。令 d 为最近的半对之间的距离。将一个半径为 O(d) 的盒子沿平分线滑动，考虑两个点都位于盒子中的中间对。
用于 3 点组合问题的 O(n log n) 时间分而治之算法根本不会有太大不同。对论证的核心是盒子始终包含 O(1) 个点，因此迭代三元组是没有问题的；合并步骤仍然是线性时间。临时密度参数(“六点”)必须被替换，但我不愿意提供细节，因为这是家庭作业，因为它实际上只需要用于分析而不需要用于实现。
关于algorithm - 在平面上找到 3 个最近的点，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/25879710/