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.
<|and make it very narrow horizontally. (This counterexample works even if both polygons are convex.) $\endgroup$ – Rahul Apr 17 '17 at 18:52