Find the nearest dot in a 2D space

Question

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)?

Answer 1

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.

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.