Tetrahedral mesh improvement, algorithms and experiments

We propose a two-step procedure to improve the quality of a three-dimensional Delaunay mesh. The first step refines the mesh by inserting sinks to remove skinny tetrahedra with large ratio between circumradius and shortest edge length. The second step eliminates remaining slivers by replacing Euclidean distance with weighted distance. We strive to maintain a balance between rigorous proofs of theoretical ideas, robust implementations of algorithms, and their practical evaluations by computational experiments.; Sink insertion is a variant of Delaunay refinement, which improves mesh quality by inserting special circumcenters, called sinks, to remove poor quality tetrahedra. We perform computational experiments to compare sink insertion with circumcenter insertion in terms of mesh quality, running time, and ease of parallelization.; The persistent appearance of slivers in large three-dimensional Delaunay meshes has been reported as early as 1985. They persist even after treatment with the Delaunay refinement algorithm. Cheng et al. proposed to remove slivers by assigning real weights to the points and change the Delaunay to the weighted Delaunay mesh. This is referred to as the sliver exudation algorithm. Their theoretical bound on the achieved minimum mesh quality is a constant that is positive but exceedingly small. We perform computational experiments to testify the practical effectiveness of sliver exudation.