General-dimensional constrained Delaunay and constrained regular triangulations. I: Combinatorial properties
The definition of Delaunay triangulation is too restrictive to comply with constraints such as discontinuity of boundary in objects rendering. In the two-dimensional case, several options are available. One can, for instance, augment the number of points and then construct the Delaunay triangulation of the enlarged vertex set, or relax the requirements for the triangles determined by the initial points. The former idea leads to the notion of conforming Delaunay triangulation; the latter to what it is improperly called constrained Delaunay triangulation (CDT). The author of the paper at hand proposes a recursive definition of CDT in higher dimensions. The motivation for choosing the properties retained in the definition, as well as the geometric justification, is carefully explained. Variants of regular triangulations are considered under the name weighted CDTs and constrained regular triangulations. As a first test of the usefulness of these notions, many basic properties are shown to be similar to well-known combinatorial properties of Delaunay triangulations. In order to verify that a triangulation is or remains a CDT, one may use the fact that the definition of CDT is local in the sense that a triangulation of a vertex set is Delaunay if and only if its facets are locally Delaunay. Additional evidence in favour of the pertinence and usefulness of the notions introduced in this paper is provided in Section 4. Here it is proved that CDTs are optimal by several criteria when used for piecewise linear interpolation. Even when it lacks such optimality, a CDT is a good starting point for mesh improvements algorithms. The paper ends with the difficult proof of a result that points out a sufficient condition for the existence of a CDT. However, this condition is relatively easy to enforce in three dimensions, so it is valuable in geometric modeling of three-dimensional objects. The results proved in this article provide foundations for correctness of algorithms for constructing and updating higher-dimensional CDTs, algorithms that will be described in later work.
- General-dimensional constrained Delaunay and constrained regular triangulations. I: Combinatorial properties
- Constrained Delaunay triangulations
- Updating and constructing constrained Delaunay and constrained regular triangulations by flips
- Towards a definition of higher order constrained Delaunay triangulations
- scientific article; zbMATH DE number 590296
- A New Look at Euler's Theorem for Polyhedra
- An acyclicity theorem for cell complexes in d dimensions
- An upper bound for conforming Delaunay triangulations
- Approximating constrained tetrahedrizations
- Conforming Delaunay triangulations in 3D
- Constrained Delaunay triangulations
- Delaunay refinement algorithms for triangular mesh generation
- Generalized Delaunay triangulation for planar graphs
- Generating well-shaped Delaunay meshes in 3D
- scientific article; zbMATH DE number 3128853 (Why is no real title available?)
- scientific article; zbMATH DE number 1183273 (Why is no real title available?)
- scientific article; zbMATH DE number 3633698 (Why is no real title available?)
- scientific article; zbMATH DE number 2079352 (Why is no real title available?)
- scientific article; zbMATH DE number 3016052 (Why is no real title available?)
- scientific article; zbMATH DE number 2119655 (Why is no real title available?)
- scientific article; zbMATH DE number 1445289 (Why is no real title available?)
- Incremental topological flipping works for regular triangulations
- Lectures on Polytopes
- Long and Thin Triangles Can Be Good for Linear Interpolation
- Mesh generation for domains with small angles
- Minimal roughness property of the Delaunay triangulation
- Minimal roughness property of the Delaunay triangulation: A shorter approach
- On Optimal Interpolation Triangle Incidences
- On the difficulty of triangulating three-dimensional nonconvex polyhedra
- Power Diagrams: Properties, Algorithms and Applications
- Pseudotriangulations from Surfaces and a Novel Type of Edge Flip
- Silver exudation
- Simulation of simplicity: a technique to cope with degenerate cases in geometric algorithms
- The Error in Linear Interpolation at the Vertices of a Simplex
- Voronoi diagrams and arrangements
- Voronoi diagrams from convex hulls
- Towards a definition of higher order constrained Delaunay triangulations
- Constrained Delaunay triangulations
- Constrained higher order Delaunay triangulations
- Mesh generation for periodic 3D microstructure models and computation of effective properties
- Why do we need Voronoi cells and Delaunay meshes? Essential properties of the Voronoi finite volume method
- Fast segment insertion and incremental construction of constrained Delaunay triangulations
- Feature-aware reconstruction of trimmed splines using Ricci flow with metric optimization
- Interpolation error estimates for harmonic coordinates on polytopes
- 3D boundary recovery by constrained Delaunay tetrahedralization
- Variational generation of prismatic boundary-layer meshes for biomedical computing
- A new incompressibility discretization for a hybrid particle MAC grid representation with surface tension
- Adaptive tetrahedral mesh generation by constrained Delaunay refinement
- General-dimensional constrained Delaunay and constrained regular triangulations. I: Combinatorial properties
- A faster circle-sweep Delaunay triangulation algorithm
- scientific article; zbMATH DE number 590296 (Why is no real title available?)
- Triangulation sous contraintes en dimension quelconque
- Why do we need Voronoi cells and Delaunay meshes?
- TetGen, a Delaunay-based quality tetrahedral mesh generator
- Updating and constructing constrained Delaunay and constrained regular triangulations by flips
- Restricted delaunay triangulations and normal cycle
- Generalizing CGAL Periodic Delaunay Triangulations
- Computational Science and Its Applications – ICCSA 2004
- A Posteriori Error Estimates for Discontinuous Galerkin Methods on Polygonal and Polyhedral Meshes
- Delaunay and regular triangulations as lexicographic optimal chains
- Differential constraints for bounded recursive identification with multivariate splines
- Reinforcement learning control with function approximation via multivariate simplex splines
- Meshfree finite difference solution of homogeneous Dirichlet problems of the fractional Laplacian
- Incrementally constructing and updating constrained Delaunay tetrahedralizations with finite precision coordinates
This page was built for publication: General-dimensional constrained Delaunay and constrained regular triangulations. I: Combinatorial properties
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2482216)
