Optimal voronoi diagram construction with n convex sites in three dimensions

Paul Harrington, Colm Ó Dúnlaing, Chee K. Yap

Research output: Contribution to journalArticlepeer-review


This paper presents a worst-case optimal algorithm for constructing the Voronoi diagram for n disjoint convex and rounded semi-algebraic sites in 3 dimensions. Rather than extending optimal 2-dimensional methods, 32,16,20,2 we base our method on a suboptimal 2-dimensional algorithm, outlined by Lee and Drysdale and modified by Sharir25,30 for computing the diagram of circular sites. For complexity considerations, we assume the sites have bounded complexity, i.e., the algebraic degree is bounded as is the number of algebraic patches making up the site. For the sake of simplicity we assume that the sites are what we call rounded. This assumption simplifies the analysis, though it is probably unnecessary. Our algorithm runs in time O(C(n)) where C(n) is the worst-case complexity of an n-site diagram. For spherical sites C(n) is θ(n2), but sharp estimates do not seem to be available for other classes of site.

Original languageEnglish (US)
Pages (from-to)555-593
Number of pages39
JournalInternational Journal of Computational Geometry and Applications
Issue number6
StatePublished - Dec 2007


  • Computational geometry
  • Convex sets
  • Voronoi diagrams

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Geometry and Topology
  • Computational Theory and Mathematics
  • Computational Mathematics
  • Applied Mathematics


Dive into the research topics of 'Optimal voronoi diagram construction with n convex sites in three dimensions'. Together they form a unique fingerprint.

Cite this