15th International Meshing Roundtable
Birmingham, Alabama, U.S.A.
September 17-20, 2006
Computer Science Department
Carnegie Mellon University
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