Finding Optimal Geodesic Bridges Between Two Simple Polygons
Amit M. Bhosle, Teofilo F. Gonzalez · 2011
Given two simple polygons P and Q we study the problem of finding an optimal geodesic bridge. Our problem differs from other versions of the problem where the bridge is a Euclidean bridge. An Euclidean bridge corresponds to a straight line flyover-like bridge, where as a geodesic bridge corresponds to finding a route for a ferry boat. The objective in both of these problems is to find a bridge that minimizes the distance from any point in P to any point in Q. We show that an optimal geodesic bridge always exists between a set of O(n 2) points on the boundary of the two polygons, where the total number of vertices in the polygons is O(n). Using this critical property, we present an algorithm that finds an optimal geodesic bridge (of minimum weight) in O(n 2 log n) time. Our algorithm uses as a subalgorithm a simpler O(n 2 log n) time algorithm that constructs an optimal geodesic bridge from a point to a polygon. 1