Calculating the Minimum Distance Between Two Non-Convex Polygons
See Amato, Nancy M (1994) for details of the difference between separation (sigma: σ) and closest visible vertex (CVV).
Q as the two polygons with
m vertices, respectively.
For the purposes of this discussion, a key insight is that it is enough to find the closest edge to each vertex in order to compute the minimum separation between
This means iterating over all vertices, and finding a nearest neighbour. Thus, a time complexity in
O((m + n) * log(m * n)) should be expected.