Theory of a practical delaunay meshing algorithm for a large class of domains

Siu Wing Cheng, Tamal K. Dey, Joshua Levine

Research output: Chapter in Book/Report/Conference proceedingChapter

5 Scopus citations


Recently a Delaunay refinement algorithm has been proposed that can mesh domains as general as piecewise smooth complexes. These domains include polyhedra, smooth and piecewise smooth surfaces, volumes enclosed by them, and above all non-manifold spaces. The algorithm is guaranteed to capture the input topology at the expense of four tests, some of which are computationally intensive and hard to implement. The goal of this paper is to present the theory that justifies a refinement algorithm with a single disk test in place of four tests of the previous algorithm. The algorithm is supplied with a resolution parameter that controls the level of refinement. We prove that, when the resolution is fine enough (this level is reached very fast in practice), the output mesh becomes homeomorphic to the input while preserving all input features. Moreover, regardless of the refinement level, each k-manifold element in the input complex ismeshed with a triangulated k-manifold. Boundary incidences among elements maintain the input structure. Implementation results reported in a companion paper corroborate our claims.

Original languageEnglish (US)
Title of host publicationAlgorithms, Architectures And Information Systems Security
PublisherWorld Scientific Publishing Co.
Number of pages18
ISBN (Electronic)9789812836243
StatePublished - Jan 1 2008
Externally publishedYes

ASJC Scopus subject areas

  • Computer Science(all)
  • Engineering(all)


Dive into the research topics of 'Theory of a practical delaunay meshing algorithm for a large class of domains'. Together they form a unique fingerprint.

Cite this