What is the fastest algorithm to calculate the minimum distance between two sets of points?

by

Perhaps you should check out (PDF warning! Also note that, for some reason, the order of the pages is reversed) “Optimal Algorithms for Computing the Minimum Distance Between Two Finite Planar Sets” by Toussaint and Bhattacharya:

It is shown in this paper that the
minimum distance between two finite
planar sets if [sic] n points can be
computed in O(n log n) worst-case
running time and that this is optimal
to within a constant factor.
Furthermore, when the sets form a
convex polygon this complexity can be
reduced to O(n).

If the two polygons are crossing convex ones, perhaps you should also check out (PDF warning! Again, the order of the pages is reversed) “An Optimal Algorithm for Computing the Minimum Vertex Distance Between Two Crossing Convex Polygons” by Toussaint:

Let P = {p1,
p2,…, pm} and Q = {q1, q2,…,
qn} be two intersecting polygons whose vertices are specified
by their cartesian coordinates in
order. An optimal O(m + n)
algorithm is presented for computing
the minimum euclidean distance between
a vertex pi in P and a
vertex qj in Q.

More Related Contents:

  1. An algorithm for inflating/deflating (offsetting, buffering) polygons
  2. Sort points in clockwise order?
  3. How do I efficiently determine if a polygon is convex, non-convex or complex?
  4. Largest circle inside a non-convex polygon
  5. How to check if line segment intersects a rectangle?
  6. What is the most efficient algorithm to find a straight line that goes through most points?
  7. How can I create an internal spiral for a polygon?
  8. Find if a point is inside a convex hull for a set of points without computing the hull itself
  9. Compute the area of intersection between a circle and a triangle?
  10. Location of highest density on a sphere
  11. Circle line-segment collision detection algorithm?
  12. Algorithm for finding the fewest rectangles to cover a set of rectangles without overlapping
  13. How do I calculate the area of a 2d polygon?
  14. Algorithm to detect intersection of two rectangles?
  15. Simple calculations for working with lat/lon and km distance?
  16. Finding whether a point lies inside a rectangle or not
  17. How do you calculate the average of a set of circular data? [closed]
  18. What is an Efficient algorithm to find Area of Overlapping Rectangles
  19. Puzzle: Find largest rectangle (maximal rectangle problem)
  20. robust algorithm for surface reconstruction from 3D point cloud?
  21. Calculate largest inscribed rectangle in a rotated rectangle
  22. Shortest distance between points algorithm
  23. Sort Four Points in Clockwise Order
  24. Polygon enclosing a set of points
  25. Create non-intersecting polygon passing through all given points
  26. Circular approximation of polygon (or its part)
  27. Best way to find a point on a circle closest to a given point
  28. What is the algorithm for finding the center of a circle from three points?
  29. Algorithm for reflecting a point across a line
  30. How can I perform Collision Detection on rotated rectangles? [closed]

Leave a Comment