Exact and approximation algorithms for finding an optimal bridge connecting two simple polygons

摘要

Given two simple polygons P and Q we define the weight of a bridge (p, q), with p is an element of rho(p) and q is an element of rho(Q), where rho() denotes the compact region enclosed by the boundary of the polygon, between the two polygons as gd(p, P) + d(p, q) + gd(q, Q), where d(p, q) is the Euclidean distance between the points p and q, and gd(x, X) is the geodesic distance between x and its geodesic furthest neighbor on X. Our problem differs from another version of the problem where the additional restriction of requiring the endpoints of the bridge to be mutually visible was imposed. We show that an optimal bridge always exists such that the endpoints of the bridge lie on the boundaries of the two polygons. Using this critical property, we present an algorithm to find an optimal bridge (of minimum weight) in O(n(2) log n) time. We present a polynomial time approximation scheme that for any epsilon > 0 generates a bridge with objective function within a factor of 1 + epsilon of the optimal value in O(kn log kn) time, where k = 2 * [1/log(1+epsilon)]. An improved polynomial time approximation scheme and algorithms for generalized versions of our problems are also discussed.