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

Question

I wanna find the minimum distance between two polygon. I mean, I have to find the minimum of shortest distance between each vertex of first shape with the all the vertexes of the other one. Something like Hausdorff Distance but I need minimum instead of maximum. I appreciate any suggestion. Thank you.

Answer 1

To start with, "shortest distance between two polygons" sounds to me like shortest distance between one point in the first polygon to another point within the second polygon. (Which may not actually be two vertices!)

Anyway, if you want to find the shortest distance between two vertices from the two polygons, then you'll have to have a look at all pairs of vertices. That is, you can't do much better than the naive n² algorithm. (Unless you exploit some geometrical properties of the polygons like convexity, if you happen to have that.)

Answer 2

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 = {p₁, p₂,..., p_m} and Q = {q₁, q₂,..., q_n} 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 p_i in P and a vertex q_j in Q.