鉴于2D点的列表中，找到最接近点到所有其他点 [英] Given list of 2d points, find the point closest to all other points

问题描述

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)

这是一个有效的算法找到该点最接近的所有其他点。

What is an efficient algorithm to find the point that is closest to all other points.

我只能想到一个蛮力澳（N ^ 2）解决方案：

I can only think of a brute force O(n^2) solution:

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)

基本上看每对点。

basically look at every pair of points.

推荐答案

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

Note that in 1-D the point that minimizes the sum of distances to all the points is the median.

在2-D的问题，可以在解决为O（n log n）的如下：

In 2-D the problem can be solved in O(n log n) as follows:

创建x坐标的有序数组和对数组中的每个元素计算选择该坐标的水平费用。一个元件的水平成本是距离的所有投影到X轴上的点的总和。这可以通过扫描该阵列两次（一次左到右，一次在相反方向）来计算线性时间。类似地创建y坐标的有序数组和对数组中的每个元素计算选择该坐标的垂直成本。

Create a sorted array of x-coordinates and for each element in the array compute the "horizontal" cost of choosing that coordinate. The horizontal cost of an element is the sum of distances to all the points projected onto the X-axis. This can be computed in linear time by scanning the array twice (once from left to right and once in the reverse direction). Similarly create a sorted array of y-coordinates and for each element in the array compute the "vertical" cost of choosing that coordinate.

现在对原始阵列中的每个点，我们可以通过添加的水平和垂直的成本计算的总费用的所有其他点 O（1）时间。因此，我们可以计算出在 O（n）的最佳点。因此，总运行时间为为O（n log n）的。

Now for each point in the original array, we can compute the total cost to all other points in O(1) time by adding the horizontal and vertical costs. So we can compute the optimal point in O(n). Thus the total running time is O(n log n).

这篇关于鉴于2D点的列表中，找到最接近点到所有其他点的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！