Partitioning a convex polygon to minimize the maximum of diameters

被引：0

作者：

Alsuwaiyel, HH ^{[1
]}

机构：

[1] King Fahd Univ Petr & Minerals, Dept Informat & Comp Sci, Dhahran 31261, Saudi Arabia

来源：

INTERNATIONAL CONFERENCE ON IMAGING SCIENCE, SYSTEMS, AND TECHNOLOGY, PROCEEDINGS | 1999年

关键词：

algorithms; computational geometry; cover polygon; diameter; maximum of diameters;

D O I：

暂无

中图分类号：

TP18 [人工智能理论];

学科分类号：

081104 ; 0812 ; 0835 ; 1405 ;

摘要：

We consider the problem of bipartitioning a convex polygon P at its vertices into two convex polygons P-1 and P-2 such that the maximum of the diameters of P1 and Pt is minimum among all partitions. We derive a divide-and-conquer algorithm that runs in time O(n(2)) in the worst case and O(n logn) on the average.

引用

页码：572 / 575

页数：4

共 50 条

[1] A parrallel algorithm for partitioning a point set to minimize the maximum of diameters
Alsuwaiyel, MH
INTERNATIONAL CONFERENCE ON PARALLEL AND DISTRIBUTED PROCESSING TECHNIQUES AND APPLICATIONS, VOLS I-IV, PROCEEDINGS, 1998, : 698 - 701
[2] A parallel algorithm for partitioning a point set to minimize the maximum of diameters
Alsuwaiyel, MH
JOURNAL OF PARALLEL AND DISTRIBUTED COMPUTING, 2001, 61 (05) : 662 - 666
[3] PARTITIONING A MATRIX TO MINIMIZE THE MAXIMUM COST
MINGOZZI, A
RICCIARDELLI, S
SPADONI, M
DISCRETE APPLIED MATHEMATICS, 1995, 62 (1-3) : 221 - 248
[4] Partitioning a matrix to minimize the maximum cost
1600, Elsevier Science B.V., Amsterdam, Netherlands (62): : 1 - 3
[5] Finding the maximum grid convex polygon for a convex region on the plane
Tseng, SY
King, CT
Tang, CY
INFORMATION SCIENCES, 1997, 98 (1-4) : 27 - 42
[6] Translating a convex polygon to contain a maximum number of points
Barequet, G
Dickerson, M
Pau, P
COMPUTATIONAL GEOMETRY-THEORY AND APPLICATIONS, 1997, 8 (04): : 167 - 179
[7] Maximum-area triangle in a convex polygon, revisited
van der Hoog, Ivor
Keikha, Vahideh
Loffler, Maarten
Mohades, Ali
Urhausen, Jerome
INFORMATION PROCESSING LETTERS, 2020, 161
[8] Sequential and parallel algorithms for finding a maximum convex polygon
Fischer, P
COMPUTATIONAL GEOMETRY-THEORY AND APPLICATIONS, 1997, 7 (03): : 187 - 200
[9] COMPUTING A MAXIMUM AXIS-ALIGNED RECTANGLE IN A CONVEX POLYGON
FISCHER, P
HOFFGEN, KU
INFORMATION PROCESSING LETTERS, 1994, 51 (04) : 189 - 193
[10] THE MAXIMUM SIZE OF A CONVEX POLYGON IN A RESTRICTED SET OF POINTS IN THE PLANE
ALON, N
KATCHALSKI, M
PULLEYBLANK, WR
DISCRETE & COMPUTATIONAL GEOMETRY, 1989, 4 (03) : 245 - 251

← 1 2 3 4 5 →