A Nearly Optimal Deterministic Parallel Voronoi Diagram Algorithm

R. Cole, M. T. Goodrich, C. Ó Dúnlaing

Research output: Contribution to journalArticle

Abstract

We describe an n-processor, O (log(n) log log(n))-time CRCW algorithm to construct the Voronoi diagram for a set of n point-sites in the plane.

Original languageEnglish (US)
Pages (from-to)569-617
Number of pages49
JournalAlgorithmica (New York)
Volume16
Issue number6
StatePublished - Dec 1996

Keywords

  • Parallel algorithm
  • Voronoi diagram

ASJC Scopus subject areas

  • Computer Science(all)
  • Computer Science Applications
  • Applied Mathematics

Fingerprint Dive into the research topics of 'A Nearly Optimal Deterministic Parallel Voronoi Diagram Algorithm'. Together they form a unique fingerprint.

  • Cite this

    Cole, R., Goodrich, M. T., & Dúnlaing, C. Ó. (1996). A Nearly Optimal Deterministic Parallel Voronoi Diagram Algorithm. Algorithmica (New York), 16(6), 569-617.