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 条
  • [31] On a triangle with the maximum area in a planar point set
    Hosono, K
    Hurtado, F
    Urabe, M
    Urrutia, J
    COMBINATORIAL GEOMETRY AND GRAPH THEORY, 2005, 3330 : 102 - 107
  • [32] A Finite Control Set Model Predictive Control Algorithm for PV Maximum Power Point Tracking
    Liu, Yue
    Wang, Chun Sheng
    Cao, Yuan
    2022 9TH INTERNATIONAL FORUM ON ELECTRICAL ENGINEERING AND AUTOMATION, IFEEA, 2022, : 1018 - 1022
  • [33] On the maximum area pentagon in a planar point set
    Du, Yatao
    Ding, Ren
    APPLIED MATHEMATICS LETTERS, 2006, 19 (11) : 1228 - 1236
  • [34] A genetic algorithm to minimize maximum lateness on a batch processing machine
    Wang, CS
    Uzsoy, R
    COMPUTERS & OPERATIONS RESEARCH, 2002, 29 (12) : 1621 - 1640
  • [35] A binary branch and bound algorithm to minimize maximum scheduling cost
    Chandra, Charu
    Liu, Zhixin
    He, Jun
    Ruohonen, Toni
    OMEGA-INTERNATIONAL JOURNAL OF MANAGEMENT SCIENCE, 2014, 42 (01): : 9 - 15
  • [36] A binary branch and bound algorithm to minimize maximum scheduling cost
    Chandra, Charu
    Liu, Zhixin
    He, Jun
    Ruohonen, Toni
    Omega (United Kingdom), 2014, 42 (01) : 9 - 15
  • [37] Partitioning a planar point set into empty convex polygons
    Ding, R
    Hosono, K
    Urabe, M
    Xu, CQ
    DISCRETE AND COMPUTATIONAL GEOMETRY, 2002, 2866 : 129 - 134
  • [38] SET-COVERING PROBLEM .2. ALGORITHM FOR SET PARTITIONING
    BALAS, E
    PADBERG, M
    OPERATIONS RESEARCH, 1975, 23 (01) : 74 - 90
  • [39] A spectral partitioning algorithm for maximum directed cut problem
    Zhenning Zhang
    Donglei Du
    Chenchen Wu
    Dachuan Xu
    Dongmei Zhang
    Journal of Combinatorial Optimization, 2021, 42 : 373 - 395
  • [40] A Spectral Partitioning Algorithm for Maximum Directed Cut Problem
    Zhang, Zhenning
    Du, Donglei
    Wu, Chenchen
    Xu, Dachuan
    Zhang, Dongmei
    COMBINATORIAL OPTIMIZATION AND APPLICATIONS, COCOA 2017, PT I, 2017, 10627 : 298 - 312
12345