Shortest distance between points algorithm

algorithm math computational-geometry
geord picture geord · Oct 21, 2009 · Viewed 32.7k times · Source

Given a set of points on a plane, find the shortest line segment formed by any two of these points.

How can I do that? The trivial way is obviously to calculate each distance, but I need another algorithm to compare.

Answer

Wayne Sheppard picture Wayne Sheppard · Oct 21, 2009

http://en.wikipedia.org/wiki/Closest_pair_of_points

The problem can be solved in O(n log n) time using the recursive divide and conquer approach, e.g., as follows:

  • Sort points along the x-coordinate
  • Split the set of points into two equal-sized subsets by a vertical line x = xmid
  • Solve the problem recursively in the left and right subsets. This will give the left-side and right-side minimal distances dLmin and dRmin respectively.
  • Find the minimal distance dLRmin among the pair of points in which one point lies on the left of the dividing vertical and the second point lies to the right.
  • The final answer is the minimum among dLmin, dRmin, and dLRmin.

Related questions

Sort points in clockwise order?

Given an array of x,y points, how do I sort the points of this array in clockwise order (around their overall average center point)? My goal is to pass the points to a line-creation function to end up with …

Read More
How to check if a point (x,y) is inside a polygon in the Cartesian coordinate system?

This question already has an answer here: Point in Polygon aka hit test C# Point in polygon Given a random polygon formulated with N line equations in the Cartesian coordinate system, is there any standard formula that is used to …

Read More
Algorithm to compute a Voronoi diagram on a sphere?

I'm looking for a simple (if exists) algorithm to find the Voronoi diagram for a set of points on the surface of a sphere. Source code would be great. I'm a Delphi man (yes, I know...), but I eat C-code …

Read More