Find the nearest dot in a 2D space

user_171230 0
Viewed 7295

Yesterday I read a problem which can be translated into the following problem with slight modification:

The coordinate of a dot is expressed by (x, y) in a 2D space.

Input : An array of dots ARRAY = (x1, y1), (x2, y2), (x3, y3), ..., (xn, yn) and another dot D = (xi, yi)

Find the dot in the ARRAY which is nearest to D.

By saying "nearest", I am referring to the Euclidian distance.

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.

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.

Generalization of the problem: how to find the nearest dot in a K-dimensional space? Can we do it in less than O(N)?

algorithm
4 Answers

Practically we can sort the points in x-coordinate, then start from the point whose x difference is most closed to the target, and we scan to both left and right, and stop scanning to one direction as soon as the next point's x difference in that direct is already bigger than smallest distance found so far. Divide Conquer is still linear if you divide to two half but do not discard either half.

user_105334160
Related