Quality Meshing with Weighted Delaunay Refinement
- 1 January 2003
- journal article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Computing
- Vol. 33 (1), 69-93
- https://doi.org/10.1137/s0097539703418808
Abstract
Delaunay meshes with bounded circumradius to shortest edge length ratio have been proposed in the past for quality meshing. The only poor quality tetrahedra, called slivers, that can occur in such a mesh can be eliminated by the sliver exudation method. This method has been shown to work for periodic point sets, but not with boundaries. Recently a randomized point-placement strategy has been proposed to remove slivers while conforming to a given boundary. In this paper we present a deterministic algorithm for generating a weighted Delaunay mesh which respects the input boundary and has no poor quality tetrahedron including slivers. As in previous work, we assume that no input angle is acute. Our result is achieved by combining the weight pumping method for sliver exudation and the Delaunay refinement method for boundary conformationKeywords
This publication has 11 references indexed in Scilit:
- Geometry and Topology for Mesh GenerationPublished by Cambridge University Press (CUP) ,2001
- Sliver exudationJournal of the ACM, 2000
- Quality Mesh Generation in Higher DimensionsSIAM Journal on Computing, 2000
- Extremal Problems for Geometric HypergraphsDiscrete & Computational Geometry, 1998
- Geometric Separators for Finite-Element MeshesSIAM Journal on Scientific Computing, 1998
- A Delaunay Refinement Algorithm for Quality 2-Dimensional Mesh GenerationJournal of Algorithms, 1995
- Provably good mesh generationJournal of Computer and System Sciences, 1994
- An optimal convex hull algorithm in any fixed dimensionDiscrete & Computational Geometry, 1993
- ON GOOD TRIANGULATIONS IN THREE DIMENSIONSInternational Journal of Computational Geometry & Applications, 1992
- Algorithms in Combinatorial GeometryPublished by Springer Science and Business Media LLC ,1987