TY - JOUR
T1 - Computing the optimal bridge between two convex polygons
AU - Cai, Leizhen
AU - Xu, Yinfeng
AU - Zhu, Binhai
PY - 1999/2/12
Y1 - 1999/2/12
N2 - 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(n2logn) 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.
AB - 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(n2logn) 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.
KW - Approximation
KW - Computational geometry
KW - Discrete optimization
UR - https://www.scopus.com/pages/publications/0033075662
U2 - 10.1016/s0020-0190(99)00003-4
DO - 10.1016/s0020-0190(99)00003-4
M3 - 文章
AN - SCOPUS:0033075662
SN - 0020-0190
VL - 69
SP - 127
EP - 130
JO - Information Processing Letters
JF - Information Processing Letters
IS - 3
ER -