Computer Science Department
School of Computer Science, Carnegie Mellon University


Sparse Voronoi Refinement

Benoît Hudson, Gary Miller, Todd Phillips

December 2006

Keywords: Meshing, Delaunay, Voronoi, Triangulation, Tetrahedralization

We present a new algorithm, Sparse Voronoi Refinement, that produces a conformal Delaunay mesh in arbitrary dimension with guaranteed mesh size and quality. Our algorithm runs in output-sensitive time O(n log (L/s) + m), with constants depending only on dimension and on prescribed element shape quality bounds. For a large class of inputs, including integer coordinates, this matches the optimal time bound of Θ(n log n + m). Our new technique uses interleaving: we maintain a sparse mesh as we mix the recovery of input features with the addition of Steiner vertices for quality improvement.

This technical report is the long version of an article presented at IMR 2006, and contains full proofs.

46 pages

Return to: SCS Technical Report Collection
School of Computer Science

This page maintained by