Well-Centered Triangulation
arXiv:0802.2108 · doi:10.1137/090748214
Abstract
Meshes composed of well-centered simplices have nice orthogonal dual meshes (the dual Voronoi diagram). This is useful for certain numerical algorithms that prefer such primal-dual mesh pairs. We prove that well-centered meshes also have optimality properties and relationships to Delaunay and minmax angle triangulations. We present an iterative algorithm that seeks to transform a given triangulation in two or three dimensions into a well-centered one by minimizing a cost function and moving the interior vertices while keeping the mesh connectivity and boundary vertices fixed. The cost function is a direct result of a new characterization of well-centeredness in arbitrary dimensions that we present. Ours is the first optimization-based heuristic for well-centeredness, and the first one that applies in both two and three dimensions. We show the results of applying our algorithm to small and large two-dimensional meshes, some with a complex boundary, and obtain a well-centered tetrahedralization of the cube. We also show numerical evidence that our algorithm preserves gradation and that it improves the maximum and minimum angles of acute triangulations created by the best known previous method.
Content has been added to experimental results section. Significant edits in introduction and in summary of current and previous results. Minor edits elsewhere
References in corpus (2)
Cited by in corpus (22)
- JIGSAW-GEO (1.0): locally orthogonal staggered unstructured grid generation for general circulation modelling on the sphere
- Discrete exterior calculus discretization of incompressible Navier-Stokes equations over surface simplicial meshes
- Orientational order on surfaces - the coupling of topology, geometry, and dynamics
- VoroCrust: Voronoi Meshing Without Clipping
- Non-negative mixed finite element formulations for a tensorial diffusion equation
- Discrete exterior calculus (DEC) for the surface Navier-Stokes equation
- Generalised primal-dual grids for unstructured co-volume schemes
- Simplicial Ricci Flow
- The Ericksen Model of Liquid Crystals with Colloidal and Electric Effects
- The centered dual and the maximal injectivity radius of hyperbolic surfaces
- Numerical method for Darcy flow derived using Discrete Exterior Calculus
- Acute triangulations of polyhedra and R^n
- Diamond-Kite Adaptive Quadrilateral Meshing
- Cohomologous Harmonic Cochains
- Triangulation of Simple 3D Shapes with Well-Centered Tetrahedra
- A Dihedral Acute Triangulation of the Cube
- Numerical Experiments for Darcy Flow on a Surface Using Mixed Exterior Calculus Methods
- A framework for coupled deformation-diffusion analysis with application to degradation/healing
- Coxeter groups, hyperbolic cubes, and acute triangulations
- Geometric and Combinatorial Properties of Well-Centered Triangulations in Three and Higher Dimensions
- On mesh restrictions to satisfy comparison principles, maximum principles, and the non-negative constraint: Recent developments and new results
- A new Hodge operator in Discrete Exterior Calculus. Application to fluid mechanics