A Randomized Algorithm for the Voronoi Diagram of Line Segments on Coarse-Grained Multiprocessors |
| |
| Authors: | Xiaotie Deng Binhai Zhu |
| |
| Affiliation: | (1) Department of Computer Science, York University, Toronto, Ontario, Canada M3J 1P3, and Department of Computer Science, City University of Hong Kong, Kowloon, Hong Kong., CA;(2) Department of Computer Science, City University of Hong Kong, Kowloon, Hong Kong, and Group CIC-3 Los Alamos National Laboratory, Los Alamos, NM 87545, USA., US |
| |
| 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) communication phases, with high probability for n=Ω(P 3+ε ) . Received June 1, 1997; revised March 10, 1998. |
| |
| Keywords: | . Coarse-grained parallel algorithms Voronoi diagram Computational geometry. |
| 本文献已被 SpringerLink 等数据库收录！ |
|
