algorithm - 给定二维点列表，找到最接近所有其他点的点

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

请注意，在一维空间中，到所有点的距离总和最小的点是中位数。

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

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

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