我这里有一道算法题。它不同于普通的Fermat Point problem .
给定一组 n
平面上的点,我需要找到哪一个可以最小化到其余 n-1
的距离总和点数。
有没有你知道的运行时间少于 O(n^2) 的算法?
谢谢。
最佳答案
一种解决方案是假设中位数接近平均值,并且对于接近平均值的点的子集,详尽地计算距离总和。您可以选择最接近均值的 klog(n) 个点,其中 k 是任意选择的常数(复杂度 nlog(n))。
另一种可能的解决方案是 Delaunay 三角剖分。这种三角剖分在 O(nlogn) 时间内是可能的。三角剖分生成一个图,每个点和边有一个顶点以满足德劳尼三角剖分。 进行三角测量后,您可以从任意点开始,比较该点与其相邻点的距离总和,并继续迭代移动。当当前点与其相邻点相比具有最小距离和时,您可以停止。直觉上,这将在全局最优点处停止。
关于在平面上的 n 个点中找到一个点以最小化距离总和的算法,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/8854621/