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, denoted by gd(a, b), in contrast with the Euclidean distance between a and b, 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, is minimized. We present an q'∈Q time algorithm for finding an optimal bridge between two simple polygons. This significantly improves upon the previous O(n{sup}2) time bound.
展开▼
