算法在平面中的n个点之间找到一个点以最小化距离之和

Question

我这里有算法问题.它与正常的费马点问题不同.

给定n平面中的一组点,我需要找到哪一个可以最小化到其余n-1点的距离之和.

你知道有没有算法运行少于O(n ^ 2)？

谢谢.

Answer 1

一种解决方案是假设中位数接近平均值，并且对于接近平均值的点的子集，详尽地计算距离之和。您可以选择最接近均值的 klog(n) 个点，其中 k 是任意选择的常数（复杂度 nlog(n)）。

另一种可能的解决方案是 Delaunay 三角测量。这种三角测量可以在 O(nlogn) 时间内完成。三角剖分会生成一张图，每个点有一个顶点，并且边满足德劳尼三角剖分。完成三角测量后，您可以从任意点开始，将该点与其邻居点的距离总和进行比较，然后继续迭代。当当前点与其相邻点相比具有最小距离总和时，您可以停止。直观上，这将停止在全局最优点。