Computer Science Department
School of Computer Science, Carnegie Mellon University
Sparse Voronoi Refinement
Benoît Hudson, Gary Miller, Todd Phillips
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.