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 条

[41] A counterexample to an algorithm for computing monotone hulls of simple polygons
Toussaint, Godfried T.
El Gindy, Hossam
PATTERN RECOGNITION LETTERS, 1983, 1 (04) : 219 - 222
[42] Algorithms for computing intersection and union of toleranced polygons with applications
Cazals, F
Ramkumar, GD
AI EDAM-ARTIFICIAL INTELLIGENCE FOR ENGINEERING DESIGN ANALYSIS AND MANUFACTURING, 1997, 11 (04): : 263 - 272
[43] Euclidean TSP between two nested convex obstacles
Abrahamson, J
Shokoufandeh, A
Winter, P
INFORMATION PROCESSING LETTERS, 2005, 95 (02) : 370 - 375
[44] MOVING A DISK BETWEEN POLYGONS
ROHNERT, H
ALGORITHMICA, 1991, 6 (02) : 182 - 191
[45] Interpolation error estimates for mean value coordinates over convex polygons
Rand, Alexander
Gillette, Andrew
Bajaj, Chandrajit
ADVANCES IN COMPUTATIONAL MATHEMATICS, 2013, 39 (02) : 327 - 347
[46] A novel fingerprint matching and classification schema based on nested convex polygons
Khazaei, Hamzeh
Mohades, Ali
RECENT ADVANCES ON APPLIED MATHEMATICS: PROCEEDINGS OF THE AMERICAN CONFERENCE ON APPLIED MATHEMATICS (MATH '08), 2008, : 419 - +
[47] Guarding two subclasses of orthogonal polygons
Martins, Ana Mafalda
Bajuelos, Antonio Leslie
RECENT PROGRESS IN COMPUTATIONAL SCIENCES AND ENGINEERING, VOLS 7A AND 7B, 2006, 7A-B : 372 - 375
[48] Computing Balanced Convex Partitions of Lines
Sergey Bereg
Algorithmica, 2023, 85 : 2515 - 2528
[49] Computing Balanced Convex Partitions of Lines
Bereg, Sergey
ALGORITHMICA, 2023, 85 (08) : 2515 - 2528
[50] Near optimal line segment queries in simple polygons
Bygi, Mojtaba Nouri
Ghodsi, Mohammad
JOURNAL OF DISCRETE ALGORITHMS, 2015, 35 (51-61) : 51 - 61

← 1 2 3 4 5 →