Finding an Optimal Bridge Between Two Polygons.

Let π(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 π(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' ∈ P and any q' ∈ Q, is minimized. We present an O(n log³ n) time algorithm for finding an optimal bridge between two simple polygons. This significantly improves upon the previous O(n²) 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. [ABSTRACT FROM AUTHOR]