给定2d点列表,找到最接近所有其他点的点

Question

Input: list of 2d points (x,y) where x and y are integers.

Distance: distance is defined as the Manhattan distance. 
    ie:
    def dist(p1,p2) 
         return abs(p1.x-p2.x) + abs(p1.y - p2.y)

什么是有效的算法来找到最接近所有其他点的点.

我只能想到一个暴力O(n ^ 2)解决方案:

minDist=inf
bestPoint = null
for p1 in points:
    dist = 0
    for p2 in points:
        dist+=distance(p1,p2)
    minDist = min(dist,minDist)
    bestPoint = argmin(p1, bestPoint)

基本上看每一对点.

Answer 1

注意,在1-D中,最小化到所有点的距离之和的点是中值.

在二维中,问题可以解决O(n log n)如下:

创建一个排序的x坐标数组,并为数组中的每个元素计算选择该坐标的"水平"成本.元素的水平成本是投影到X轴上的所有点的距离之和.这可以通过扫描阵列两次(一次从左到右,一次在反方向)以线性时间计算.类似地,创建一个y坐标的排序数组,并为数组中的每个元素计算选择该坐标的"垂直"成本.

现在,对于原始数组中的每个点,我们可以O(1)通过添加水平和垂直成本来计算所有其他时间点的总成本.所以我们可以计算最佳点O(n).因此总运行时间是O(n log n).