COMPUTING CONSTRAINED SHORTEST SEGMENTS: BUTTERFLY WINGSPANS IN LOGARITHMIC TIME
David G. Kirkpatrick, Jack Scott Snoeyink · International Journal of Computational Geometry & Applications · 1999
We give a logarithmic-time algorithm to compute the shortest segment joining two convex n-gons A and B while avoiding another convex n-gon C. Our algorithm uses a tentative prune-and-search technique on standard representations of the polygons as arrays or balanced binary search trees.