Efficient computation of clipped Voronoi diagram for mesh generation

Dongming Yan, Wen Ping Wang, Bruno L. Lévy, Yang Liu

Research output: Contribution to journalArticlepeer-review

42 Scopus citations

Abstract

The Voronoi diagram is a fundamental geometric structure widely used in various fields, especially in computer graphics and geometry computing. For a set of points in a compact domain (i.e. a bounded and closed 2D region or a 3D volume), some Voronoi cells of their Voronoi diagram are infinite or partially outside of the domain, 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 to compute the clipped Voronoi diagram for a set of sites with respect to a compact 2D region or a 3D volume. We also apply the proposed method to optimal mesh generation based on the centroidal Voronoi tessellation. Crown Copyright © 2011 Published by Elsevier Ltd. All rights reserved.
Original languageEnglish (US)
Pages (from-to)843-852
Number of pages10
JournalCAD Computer Aided Design
Volume45
Issue number4
DOIs
StatePublished - Apr 2013

ASJC Scopus subject areas

  • Computer Graphics and Computer-Aided Design
  • Industrial and Manufacturing Engineering
  • Computer Science Applications

Fingerprint

Dive into the research topics of 'Efficient computation of clipped Voronoi diagram for mesh generation'. Together they form a unique fingerprint.

Cite this