Find the closest point in two-dimensional space

Question

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

The coordinate of the point is expressed (x, y) in two-dimensional space.

Input: an array of points ARRAY = (x1, y1), (x2, y2), (x3, y3), ..., (xn, yn) and another point D = (xi, yi)

Find the point in ARRAY that is closest to D

When I say "closest," I mean the Euclidean distance .

---

There is an obvious solution: cross each point in ARRAY and calculate its Euclidean distance to D Then find the shortest distance. This can be done in O (N) time.

Is it possible to do faster, say, in O (logN)? I am trying to use the divide and conquer approach, but have not yet come up with a concrete idea.

---

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

Answer 1

If the array is not sorted in any way, then it is impossible to do anything faster than O (n), since you need to check every point to make sure that it is not closer than everything that you have found so far.

You can do some preprocessing to sort the points or pack them into some structure, and then search in that structure. In this case, although the preprocessing step may be slower than O (n), an individual search may be faster. If you have a lot of points to test against the same set of points, this can be beneficial.

Answer 2

You can use the Bounding Volume Hierarchy . This does not improve the complexity of the worst case, but also does not lead to an exact solution.

Answer 3

I chose a solution in O (logN) if the points are sorted by x coordinate.

He uses the divide and conquer approach. I am sharing an array of points based on their x coordinate in 2D space.

Consider the two-dimensional case.

Assume that each point is expressed in the following data structure:

 class Point { public float getX(); public float getY(); } 

We have two inputs: a point array ARRAY and another point D

Initially, we would like to divide ARRAY into two parts: those points that are on the "left" of D , and these points are on the "right" of D

 int pivotIndex = partition(array, 0, array.length() - 1, d); 

After splitting, points with an index less than pivotIndex have an x ​​coordinate less than d.getX() ; points with an index equal to or greater than pivotIndex have an x ​​coordinate equal to or greater than d.getX() .

If all points are located to the left of D , pivotIndex will be array.length() - 1 . If all points are to the right of D , pivotIndex will be -1 . If some points are located to the left of D , and some points are located to the right of D , then pivotIndex will be between 0 and array.length() - 1 . For points having the same x coordinate as D , they are treated as “right.”

Now the next step is to find the nearest point in each section:

 Point p1 = getNearestDot(array, 0, pivotIndex, d); Point p2 = getNearestDot(array, pivotIndex + 1, array.length() - 1, d); if (p1 == null) return p2; if (p2 == null) return p1; return nearer(p1, p2, d); 

It is possible that all points in ARRAY are on the left side of D , then p2 will be empty in this case. Similarly, if all points in ARRAY are on the right side of D , then p1 will be empty.

The getNearestDot algorithm works as follows:

 // Find the nearest dot in array[low...high] inclusive which is closest to point d Point getNearestDot(Point[] array, int low, int high, Point d) { if (low > high) return null; if (low == high) return array[low]; int middle = low + (high - low) >> 1; Point p1 = getNearestDot(array, low, middle, d); Point p2 = getNearestDot(array, middle + 1, high, d); if (p1 == null) return p2; if (p2 == null) return p1; return nearer(p1, p2, d); } 

And finally, the function closer (p1, p2, d) should return either p1 or p2, the distance to which d is less.