A parrallel algorithm for partitioning a point set to minimize the maximum of diameters

被引：0

作者：

Alsuwaiyel, MH ^{[1
]}

机构：

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

来源：

INTERNATIONAL CONFERENCE ON PARALLEL AND DISTRIBUTED PROCESSING TECHNIQUES AND APPLICATIONS, VOLS I-IV, PROCEEDINGS | 1998年

关键词：

computational geometry; simple polygon; diameter; maximum of diameters; parallel algorithms;

D O I：

暂无

中图分类号：

TP3 [计算技术、计算机技术];

学科分类号：

0812 ;

摘要：

Given a set S of n points ist the plane, we consider the problem of partitioning S into two subsets such that the masimum of their diameters is minimized. We present a parallel algorithm to solve this problem that runs in time O(log n log log n) using the GREW PRAM model of computation with O(n(2)) processors.

引用

页码：698 / 701

页数：4

共 50 条

[1] 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
[2] Partitioning a convex polygon to minimize the maximum of diameters
Alsuwaiyel, HH
INTERNATIONAL CONFERENCE ON IMAGING SCIENCE, SYSTEMS, AND TECHNOLOGY, PROCEEDINGS, 1999, : 572 - 575
[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] ALGORITHM FOR SET PARTITIONING PROBLEM
GONDRAN, M
LAURIERE, JL
REVUE FRANCAISE D AUTOMATIQUE INFORMATIQUE RECHERCHE OPERATIONNELLE, 1974, 8 (NV1): : 27 - 40
[6] Affine partitioning algorithm to maximize parallelism and minimize communication
Lim, Amy W.
Cheong, Gerald I.
Lam, Monica S.
Proceedings of the International Conference on Supercomputing, 1999, : 228 - 237
[7] Partitioning a matrix with non-guillotine cuts to minimize the maximum cost
Mingozzi, A
Morigi, S
DISCRETE APPLIED MATHEMATICS, 2002, 116 (03) : 243 - 260
[8] TRANSFORMATION OF SET PARTITIONING PROBLEM INTO A MAXIMUM WEIGHTED STABLE SET PROBLEM
BILLIONNET, A
RAIRO-RECHERCHE OPERATIONNELLE-OPERATIONS RESEARCH, 1978, 12 (03): : 319 - 323
[9] ALGORITHM FOR MINIMAL PARTITIONING OF THE SET SYSTEM
ORANOV, AM
ANDREEVA, LN
AVTOMATIKA I VYCHISLITELNAYA TEKHNIKA, 1992, (02): : 37 - 44
[10] An algorithm for partitioning a set into simple parts
Savel'ev, LY
PROGRAMMING AND COMPUTER SOFTWARE, 2005, 31 (06) : 293 - 300

← 1 2 3 4 5 →