查找最近的点在二维空间 [英] Find the nearest dot in a 2D space
问题描述
昨天我看了一个问题，可以翻译成以下问题略作修改：
Yesterday I read a problem which can be translated into the following problem with slight modification:
的点的坐标是由（x，y）的在二维空间pssed前$ P $。
The coordinate of a dot is expressed by (x, y) in a 2D space.
输入：点 ARRAY =（X1，Y1），（X2，Y2），（X3，Y3），数组...（XN，YN）
而另一点 D =（十一，彝族）
Input : An array of dots ARRAY = (x1, y1), (x2, y2), (x3, y3), ..., (xn, yn)
and another dot D = (xi, yi)
查找在 ARRAY 这是最接近 D 。
所说的最近，我指的是欧氏距离。
By saying "nearest", I am referring to the Euclidian distance.
有一个显而易见的解决方案：遍历每个点的 ARRAY 并计算其欧氏距离 D 。然后，找到的最短距离。这可以在O（N）的时间内完成。
There is an obvious solution: traverse each dot in the ARRAY and compute its Euclidian distance to D. Then, find the shortest distance. This can be done in O(N) time.
我们可以做的更快，可以说，在O（logN）的？我想使用分而治之的办法，但都没有得出一个具体的想法呢。
Can we do faster, say, in O(logN)? I am trying to use divide-and-conquer approach, but haven't come to a concrete idea yet.
问题的推广：如何找到最近的点在K维空间？我们能做到这一点，在不到O（N）？
Generalization of the problem: how to find the nearest dot in a K-dimensional space? Can we do it in less than O(N)?
推荐答案
如果该数组不以任何方式来分类的话，就不可能做任何速度比为O（n），因为你必须检查每一个点确保它是不是比你到目前为止发现近了。
If the array is not sorted in any way, then it is not possible to do any faster than O(n), as you have to check every point to make sure it is not closer than anything you have found so far.
您可以做一些preprocessing给分排序或打包成一定的结构，然后执行该结构的搜索。在这种情况下，当preprocessing步骤可以比为O（n）越慢，个体的搜索可能会更快。如果你有很多点，检查针对相同的点的集合，这可能是有利的。
You CAN do some preprocessing to sort the points or pack them into some structure, then do searches on that structure. In this case, while the preprocessing step may be slower than O(n), the individual searches may be faster. If you have many points to check against the same set of points, this can be advantageous.
这篇关于查找最近的点在二维空间的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
