Fully Generalized Two-Dimensional Constrained Delaunay Mesh Refinement
- 1 January 2010
- journal article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Scientific Computing
- Vol. 32 (5), 2659-2686
- https://doi.org/10.1137/090763226
Abstract
Traditional refinement algorithms insert a Steiner point from a few possible choices at each step. Our algorithm, on the contrary, defines regions from where a Steiner point can be selected and thus inserts a Steiner point among an infinite number of choices. Our algorithm significantly extends existing generalized algorithms by increasing the number and the size of these regions. The lower bound for newly created angles can be arbitrarily close to $30^{\circ}$. Both termination and good grading are guaranteed. It is the first Delaunay refinement algorithm with a $30^{\circ}$ angle bound and with grading guarantees. Experimental evaluation of our algorithm corroborates the theory.
Keywords
This publication has 6 references indexed in Scilit:
- Generalized Two-Dimensional Delaunay Mesh RefinementSIAM Journal on Scientific Computing, 2009
- Generating well-shaped d-dimensional Delaunay MeshesTheoretical Computer Science, 2003
- Delaunay refinement algorithms for triangular mesh generationComputational Geometry, 2002
- A Delaunay Refinement Algorithm for Quality 2-Dimensional Mesh GenerationJournal of Algorithms, 1995
- Computing the n-dimensional Delaunay tessellation with application to Voronoi polytopesThe Computer Journal, 1981
- Computing Dirichlet tessellationsThe Computer Journal, 1981