Given two simple polygons P and Q we study the problem of finding an optimal geodesic bridge. The objective is to find a bridge that minimizes the largest distance from any point in P to any point in Q. We present an algorithm that finds an optimal geodesic bridge (of minimum weight) in O(n 2 logn) time. Our algorithm uses as a subalgorithm a simpler O(n 2 logn) time algorithm that constructs an optimal geodesic bridge from a point to a polygon.
['Amit M. Bhosle', 'Teofilo F. Gonzalez']
Finding Optimal Geodesic Bridges Between Two Simple Polygons