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

Question

我这里有一道算法题。它不同于普通的Fermat Point problem .

给定一组 n平面上的点，我需要找到哪一个可以最小化到其余 n-1 的距离总和点数。

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

谢谢。

Answer 1

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

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