In calculating the minimum distance (in $\mathbb R ^\mathbb2$) between two disjoint non-convex polygons whose convex hulls cannot be computed without intersecting, I found Toussaint and Bhattacharya's paper for "Computing the Minimum Distance Between Finite Planar Sets".
Given two sets of points $S1$ and $S2$
- Compute the Voronoi diagram of $S$ = $S1 \cup S2$.
- From the dual of the Voronoi diagram, obtain the Gabriel graph of $S$.
- From among the edges of the Gabriel graph, determine the set of pairs of points such that one is from $S1$ and the other from $S2$.
- Compute the distance between all pairs of points in Step 3.
- Determine the minimum of the distances computed in Step 4.
This works well, but only gives me the minimum point distance; it has no notion of a polygon with a closed ring, which may have a vertex-edge distance which is closer than vertex-vertex.
What I'm wondering is whether the point pair (p1, p2) obtained using the algorithm is always involved in the minimum distance. E.g. either p1 is the vertex and p2 is one of the vertices in the closest edge, or vice versa.
Example of two polygons:
In the above polygons, the minimum distance is between the vertex at the point of the right polygon, and the upper diagonal edge of the left polygon. The algorithm returns the vertex of the right polygon, and the left vertex of the edge of the left polygon.
However, I don't know whether this is always the case for disjoint non-convex polygons.
This paper by Nancy Amato is on parallel algorithms, but it cites the sequential algorithms that achieve $O(n \log n)$ time using Voronoi diagrams.
If speed is important to you, and you don't want to go the full Voronoi-route, then you might use an R-tree to reduce the search space for the brute-force quadratic algorithm.