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

user_207180 0
Viewed 20756

I want to find the minimum distance between two polygons with million number of vertices(not the minimum distance between their vertices). I have to find the minimum of shortest distance between each vertex of first shape with all of the vertices of the other one. Something like the Hausdorff Distance, but I need the minimum instead of the maximum.

computational-geometry distance geometry algorithm
2 Answers

There is a simple algorithm that uses Minkowski Addition that allows calculating min-distance of two convex polygonal shapes and runs in O(n + m).
Links:
algoWiki, boost.org, neerc.ifmo.ru (in russian).

If Minkowski subtraction of two convex polygons covers (0, 0), then they intersect

user_155715600
Related