4
$\begingroup$

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$

  1. Compute the Voronoi diagram of $S$ = $S1 \cup S2$.
  2. From the dual of the Voronoi diagram, obtain the Gabriel graph of $S$.
  3. 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$.
  4. Compute the distance between all pairs of points in Step 3.
  5. 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:

enter image description here

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.

$\endgroup$
4
  • 1
    $\begingroup$ No, replace the left polygon with a left-pointing triangle <| and make it very narrow horizontally. (This counterexample works even if both polygons are convex.) $\endgroup$ – user856 Apr 17 '17 at 18:52
  • $\begingroup$ @Rahul I don't follow; that doesn't seem like it would confound the algorithm, which would then return one of the vertices opposite the left point, which is still part of the nearest edge. $\endgroup$ – urschrei Apr 17 '17 at 18:59
  • 1
    $\begingroup$ From the title of the paper to which you refer, they find not the minimum distance, but the minimum vertex distance. The minimum distance is always realized by a segment one end of which is at a vertex, but the other end could be interior to an edge. $\endgroup$ – Joseph O'Rourke Apr 17 '17 at 20:08
  • $\begingroup$ @JosephO'Rourke Ah, OK. Is there any way of reducing the search space using triangulation? $\endgroup$ – urschrei Apr 17 '17 at 21:34
3
$\begingroup$

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.

Amato, Nancy M. "Determining the separation of simple polygons." International Journal of Computational Geometry & Applications 4.04 (1994): 457-474. (PDF download link).
AmatoFig1

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.