Three-dimensional delaunay mesh generation

Siu Wing Cheng, Sheung Hung Poon

Research output: Journal PublicationArticlepeer-review

24 Citations (Scopus)


We propose an algorithm to compute a conforming Delaunay mesh of a bounded domain in ℝ3 specified by a piecewise linear complex. Arbitrarily small input angles are allowed, and the input complex is not required to be a manifold. Our algorithm encloses the input edges with a small buffer zone, a union of balls whose sizes are proportional to the local feature sizes at their centers. In the output mesh, the radius-edge ratio of the tetrahedra outside the buffer zone is bounded by a constant independent of the domain, while that of the tetrahedra inside the buffer zone is bounded by a constant depending on the smallest input angle. Furthermore, the output mesh is graded. Our work is the first that provides quality guarantees for Delaunay meshes in the presence of small input angles.

Original languageEnglish
Pages (from-to)419-456
Number of pages38
JournalDiscrete and Computational Geometry
Issue number3
Publication statusPublished - Oct 2006
Externally publishedYes

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Geometry and Topology
  • Discrete Mathematics and Combinatorics
  • Computational Theory and Mathematics


Dive into the research topics of 'Three-dimensional delaunay mesh generation'. Together they form a unique fingerprint.

Cite this