Finding an optimal bridge between two polygons

Let pi(a, b) denote the shortest path between two points a, b inside a simple polygon P, which totally lies in P. The geodesic distance between a and b in P is defined as the length of pi(a, b), denoted by gd(a, b), in contrast with the Euclidean distance between a and b in the plane, denoted by d(a, b), Given two disjoint polygons P and Q in the plane, the bridge problem asks for a line segment (optimal bridge) that connects a point p on the boundary of P and a point q on the boundary of Q such that the sum of three distances gd(p', p), d(p, q) and gd(q, q'), with any p' epsilon P and any q' epsilon Q, is minimized. We present an O(n log(3) n) time algorithm for finding an optimal bridge between two simple polygons. This significantly improves upon the previous O(n(2)) time bound, Our result is obtained by making substantial use of a hierarchical structure that consists of segment trees, range trees and persistent search trees, and a structure that supports dynamic ray shooting and shortest path queries as well.