An optimal expected-time parallel algorithm for Voronoi diagrams
Authors:Christos Levcopoulos, Jyrki Katajainen, and Andrzej Lingas
Published in:Proceedings of the 1st Scandinavian Workshop on Algorithm Theory, Lecture Notes in Computer Science 318, Springer-Verlag (1988), 190-198
DOI:10.1007/3-540-19487-8_21
Copyright:© Springer-Verlag
Abstract:We present a parallel algorithm which constructs the Voronoi diagram of a planar n-point set within a square window. When the points are independently drawn from a uniform distribution, the algorithm runs in O(log n) expected time on CRCW PRAM with O(n / log n) processors. The fast operation of the algorithm results from the efficiency of a new multi-level bucketing technique convenient in processor assignment. The concurrent write is used only for the distribution of points in their home buckets in the bottom level.
BibLATEX:
@inproceedings{LKL1988C,
  author = {Christos Levcopoulos and Jyrki Katajainen and Andrzej Lingas},
  title = {An optimal expected-time parallel algorithm for {V}oronoi diagrams},
  booktitle = {Proceedings of the 1st Scandinavian Workshop on Algorithm
    Theory},
  series = {Lecture Notes in Computer Science},
  volume = {318},
  publisher = {Springer-Verlag},
  year = {1988},
  pages = {190--198},
}
This page was generated by Jyrki Katajainen <jyrki@di.ku.dk> on 31.12.2011.