A nearly optimal deterministic parallel Voronoi diagram algorithm |
| |
| Authors: | R. Cole M. T. Goodrich C. Ó. Dúnlaing |
| |
| Affiliation: | (1) Department of Computer Science, Courant Institute, 251 Mercer Street, 10012 New York, NY, USA;(2) Department of Computer Science, Johns Hopkins University, 21218 Baltimore, MD, USA;(3) School of Mathematics, Trinity College, Dublin 2, Ireland |
| |
| Abstract: | ![]()
We describe ann-processor,O(log(n) log log(n))-time CRCW algorithm to construct the Voronoi diagram for a set ofn point-sites in the plane.A preliminary version of this paper was presented at the 17th EATCS ICALP meeting at Warwick, England, in July 1990.Supported by the US NSF under Grants CCR 890221 and CCR 8906949.Supported by the US NSF under Grants CCR 8810568, CCR-9003299, and IRI-9116843, and by the NSF and DARPA under Grant CCR 8908092.Supported by the EU Esprit program under BRAs 3075 (ALCOM) and 7141 (ALCOM II). |
| |
| Keywords: | Voronoi diagram Parallel algorithm |
| 本文献已被 SpringerLink 等数据库收录！ |
|
