carrier image

Sparse Voronoi Refinement

Benoit Hudson, Gary Miller, and Todd Phillips

Proceedings, 15th International Meshing Roundtable, Springer-Verlag, pp.339-356, September 17-20 2006

IMR
PROCEEDINGS

15th International Meshing Roundtable
Birmingham, Alabama, U.S.A.
September 17-20, 2006

Computer Science Department
Carnegie Mellon University

Abstract
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 T(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.

Download Full Paper (PDF Format)


Contact author(s) or publisher for availability and copyright information on above referenced article