Computing the optimal bridge between two convex polygons

We present an efficient algorithm for solving the following problem. Given two disjoint convex polygonal regions P, Q in the plane, add a line segment to connect them so as to minimize the maximum of the distances between points in one region and points in the other region. An O(n²logn) time algorithm is presented to find such a line segment (optimal bridge) (p, q), where n is the maximal cardinality of P, Q. We also present a very simple linear time constant factor approximate solution for this problem.