Efficient computation of 3D clipped Voronoi diagram

Dong Ming Yan*, Wenping Wang, Bruno Lévy, Yang Liu

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

38 Scopus citations


The Voronoi diagram is a fundamental geometry structure widely used in various fields, especially in computer graphics and geometry computing. For a set of points in a compact 3D domain (i.e. a finite 3D volume), some Voronoi cells of their Voronoi diagram are infinite, but in practice only the parts of the cells inside the domain are needed, as when computing the centroidal Voronoi tessellation. Such a Voronoi diagram confined to a compact domain is called a clipped Voronoi diagram. We present an efficient algorithm for computing the clipped Voronoi diagram for a set of sites with respect to a compact 3D volume, assuming that the volume is represented as a tetrahedral mesh. We also describe an application of the proposed method to implementing a fast method for optimal tetrahedral mesh generation based on the centroidal Voronoi tessellation.

Original languageEnglish (US)
Title of host publicationAdvances in Geometric Modeling and Processing - 6th International Conference, GMP 2010, Proceedings
Number of pages14
StatePublished - 2010
Externally publishedYes
Event6th International Conference on Advances in Geometric Modeling and Processing, GMP 2010 - Castro Urdiales, Spain
Duration: Jun 16 2010Jun 18 2010

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume6130 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Other6th International Conference on Advances in Geometric Modeling and Processing, GMP 2010
CityCastro Urdiales


  • Delaunay triangulation
  • Voronoi diagram
  • centroidal Voronoi tessellation
  • tetrahedral meshing

ASJC Scopus subject areas

  • Theoretical Computer Science
  • General Computer Science


Dive into the research topics of 'Efficient computation of 3D clipped Voronoi diagram'. Together they form a unique fingerprint.

Cite this