Computing the optimal bridge between two convex polygons

被引：10
|
作者：
Cai, LZ
Xu, YF
Zhu, BH [1 ]
机构：
[1] City Univ Hong Kong, Dept Comp Sci, Kowloon, Peoples R China
[2] Chinese Univ Hong Kong, Dept Comp Engn & Sci, Shatin, Peoples R China
[3] Xi An Jiao Tong Univ, Sch Management, Xian, Peoples R China
[4] Laurentian Univ, Dept Math & Comp Sci, Sudbury, ON P3E 2C6, Canada
来源：
INFORMATION PROCESSING LETTERS | 1999年 / 69卷 / 03期
关键词：
computational geometry; discrete optimization; approximation;
D O I：
10.1016/S0020-0190(99)00003-4
中图分类号：
TP [自动化技术、计算机技术];
学科分类号：
0812 ;
摘要：
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(2) log n) time algorithm is presented to find such a line segment (optimal bridge) (p, q), where n is the maximal cardinality of P, e. We also present a very simple linear time constant factor approximate solution for this problem. (C) 1999 Elsevier Science B.V. All rights reserved.
引用
收藏
页码：127 / 130
页数：4
相关论文
共 50 条
12345