Approximation Algorithms for Finding the Optimal Bridge Connecting Two Simple Polygons

Report ID:
2003-36
Authors:
Amit M. Bhosle and Teofilo F. Gonzalez
Date:
2003-10-01 05:00:00

Abstract

Given two simple polygons $P$ and $Q$ we definethe weight of a bridge $(p,q)$, with $p\\in \\delta(P)$ and$q\\in \\delta(Q)$, where $\\delta()$ defines the boundary of thepolygon, 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(a,A)$ is the geodesic distance between $a$ andits geodesic farthest neighbor on $A$. An optimal bridge (ofminimum weight) can be found in $O(n \\log ^3n)$ time as describedin \\cite{tan}. We present an approximation scheme that, given anypositive integer $k$, constructs a bridge with objective functionvalue within $(1 + \\frac{2}{k+1})$ of optimal in $O(kn \\log kn)$time, thus solving an open problem stated in \\cite{kim}.We also present a fully polynomial time approximation scheme thatfor any $\\epsilon >0$ generates a bridge with objective functionwithin $\\epsilon$ of optimal in $O(kn \\log kn)$ time, where$k = 2*\\lceil \\frac{1}{\\log (1+\\epsilon)} \\rceil$. In contrast tothe exact algorithm given in \\cite{tan}, our algorithm does notuse complicated data structures and is amenable to efficientimplementations. We also show that the claim of \\cite{tan} that if$(p,q)$ is the optimal bridge, then $gd(p,q) = d(p,q)$ is incorrect.