A randomized algorithm for the Voronoi diagram of line segments on coarse-grained multiprocessors

被引：5
作者：
Deng, XT [1 ]
Zhu, BH
机构：
[1] York Univ, Dept Comp Sci, N York, ON M3J 1P3, Canada
[2] City Univ Hong Kong, Dept Comp Sci, Kowloon, Peoples R China
[3] Los Alamos Natl Lab, Grp CIC3, Los Alamos, NM 87545 USA
来源：
ALGORITHMICA | 1999年 / 24卷 / 3-4期
关键词：
coarse-grained parallel algorithms; Voronoi diagram; computational geometry;
D O I：
10.1007/PL00008263
中图分类号：
TP31 [计算机软件];
学科分类号：
081202 ; 0835 ;
摘要：
We present a randomized algorithm for computing the Voronoi diagram of line segments using coarse-grained parallel machines. Operating on P processors, for any input of n line segments, this algorithm performs O((n log n)/P) local operations per processor, O(n/P) messages per processor, and O(1) communication phases, with high probability for n = Omega (P3+epsilon).
引用
收藏
页码：270 / 286
页数：17
相关论文
共 37 条
  • [1] Amato N. M., 1994, Proceedings. 35th Annual Symposium on Foundations of Computer Science (Cat. No.94CH35717), P683, DOI 10.1109/SFCS.1994.365724
  • [2] [Anonymous], P 3 SPAA
  • [3] [Anonymous], P 6 ANN ACM S PAR AL
  • [4] CHAN MTV, 1994, J CLIN ANESTH, V6, P263, DOI 10.1016/0952-8180(94)90070-1
  • [5] CHAZELLE B, 1991, LECT NOTES COMPUT SC, V510, P661
  • [6] ALGORITHMS FOR BICHROMATIC LINE-SEGMENT PROBLEMS AND POLYHEDRAL TERRAINS
    CHAZELLE, B
    EDELSBRUNNER, H
    GUIBAS, LJ
    SHARIR, M
    [J]. ALGORITHMICA, 1994, 11 (02) : 116 - 132
  • [7] QUASI-OPTIMAL RANGE SEARCHING IN SPACES OF FINITE VC-DIMENSION
    CHAZELLE, B
    WELZL, E
    [J]. DISCRETE & COMPUTATIONAL GEOMETRY, 1989, 4 (05) : 467 - 489
  • [8] CULLER D, 1993, P 4 ACM SIGPLAN S PR, P1
  • [9] Dehne F., 1994, Proceedings. Sixth IEEE Symposium on Parallel and Distributed Processing (Cat. No.94TH0675-9), P586, DOI 10.1109/SPDP.1994.346119
  • [10] DEHNE F., 1995, P ACM S PAR ALG ARCH, P27
1234