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

Authors
Deng, XT Zhu, BH
Citation
Xt. Deng et Bh. Zhu, A randomized algorithm for the Voronoi diagram of line segments on coarse-grained multiprocessors, ALGORITHMIC, 24(3-4), 1999, pp. 270-286
Citations number
37
Categorie Soggetti
Engineering Mathematics
Journal title
ALGORITHMICA
ISSN journal
01784617 → ACNP
Volume
24
Issue
3-4
Year of publication
1999
Pages
270 - 286
Database
ISI
SICI code
0178-4617(199907/08)24:3-4<270:ARAFTV>2.0.ZU;2-H
Abstract
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) com munication phases, with high probability for n = Omega (P3+epsilon).