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 条

[31] COMPUTING DEVIATIONS FROM CONVEXITY IN POLYGONS
BOXER, L
PATTERN RECOGNITION LETTERS, 1993, 14 (03) : 163 - 167
[32] Algorithm for approximation transitional developable surfaces between two polygons
Obradovic, Ratko
Popkonstantinovic, Branislav
Beljin, Branislav
TECHNICS TECHNOLOGIES EDUCATION MANAGEMENT-TTEM, 2012, 7 (04): : 1907 - 1913
[33] Affine Properties of Convex Equal-Area Polygons
Craizer, Marcos
Teixeira, Ralph C.
da Silva, Moacyr A. H. B.
DISCRETE & COMPUTATIONAL GEOMETRY, 2012, 48 (03) : 580 - 595
[34] Edge advancing rules for intersecting spherical convex polygons
Ha, JS
Shin, SY
INTERNATIONAL JOURNAL OF COMPUTATIONAL GEOMETRY & APPLICATIONS, 2002, 12 (03) : 207 - 216
[35] Two efficient algorithms for determining intersection points between simple polygons
Zalik, B
COMPUTERS & GEOSCIENCES, 2000, 26 (02) : 137 - 151
[36] A simple proof of Pach's Extremal Theorem for convex polygons
Toussaint, Godfried T.
PATTERN RECOGNITION LETTERS, 1982, 1 (02) : 85 - 86
[37] An Efficient Algorithm for Touring a Sequence of given Convex Polygons in the Plane
Xu, Changan
Jiang, Bo
Wang, Lijuan
PROCEEDINGS OF 2017 6TH INTERNATIONAL CONFERENCE ON COMPUTER SCIENCE AND NETWORK TECHNOLOGY (ICCSNT 2017), 2017, : 74 - 78
[38] Euclidean TSP on two polygons
Abrahamson, Jeff
Shokoufandeh, Ali
THEORETICAL COMPUTER SCIENCE, 2010, 411 (7-9) : 1104 - 1114
[39] BISECTIONS AND HAM-SANDWICH CUTS OF CONVEX POLYGONS AND POLYHEDRA
STOJMENOVIC, I
INFORMATION PROCESSING LETTERS, 1991, 38 (01) : 15 - 21
[40] Faster counting empty convex polygons in a planar point set
Bae, Sang Won
INFORMATION PROCESSING LETTERS, 2022, 175

← 1 2 3 4 5 →