General-dimensional constrained Delaunay and constrained regular triangulations. I: Combinatorial properties

DOI10.1007/S00454-008-9060-3zbMath1142.52010OpenAlexW1997071543MaRDI QIDQ2482216

Jonathan Richard Shewchuk

Publication date: 16 April 2008

Published in: Discrete \& Computational Geometry (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00454-008-9060-3

zbMATH Keywords

piecewise linear interpolationDelaunay triangulationconstrained Delaunay triangulationregular triangulationDelaunay Lemmapiecewise linear complexes

Mathematics Subject Classification ID

Numerical aspects of computer graphics, image analysis, and computational geometry (65D18) Packing and covering in (2) dimensions (aspects of discrete geometry) (52C15) Combinatorial aspects of tessellation and tiling problems (05B45)

Related Items (14)

Mesh generation for periodic 3D microstructure models and computation of effective properties ⋮ A new incompressibility discretization for a hybrid particle MAC grid representation with surface tension ⋮ A Posteriori Error Estimates for Discontinuous Galerkin Methods on Polygonal and Polyhedral Meshes ⋮ Feature-aware reconstruction of trimmed splines using Ricci flow with metric optimization ⋮ Why Do We Need Voronoi Cells and Delaunay Meshes? ⋮ A faster circle-sweep Delaunay triangulation algorithm ⋮ Why do we need Voronoi cells and Delaunay meshes? Essential properties of the Voronoi finite volume method ⋮ Differential constraints for bounded recursive identification with multivariate splines ⋮ 3D boundary recovery by constrained Delaunay tetrahedralization ⋮ Adaptive tetrahedral mesh generation by constrained Delaunay refinement ⋮ Interpolation error estimates for harmonic coordinates on polytopes ⋮ Variational generation of prismatic boundary-layer meshes for biomedical computing ⋮ TetGen, a Delaunay-Based Quality Tetrahedral Mesh Generator ⋮ Fast segment insertion and incremental construction of constrained Delaunay triangulations

Uses Software

• Triangle
• Voronoi

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• An upper bound for conforming Delaunay triangulations
• Minimal roughness property of the Delaunay triangulation
• An acyclicity theorem for cell complexes in d dimensions
• Generalized Delaunay triangulation for planar graphs
• Voronoi diagrams and arrangements
• Constrained Delaunay triangulations
• Voronoi diagrams from convex hulls
• On the difficulty of triangulating three-dimensional nonconvex polyhedra
• Minimal roughness property of the Delaunay triangulation: A shorter approach
• Approximating constrained tetrahedrizations
• Delaunay refinement algorithms for triangular mesh generation
• Incremental topological flipping works for regular triangulations
• Sliver exudation
• Simulation of simplicity: a technique to cope with degenerate cases in geometric algorithms
• On Optimal Interpolation Triangle Incidences
• Long and Thin Triangles Can Be Good for Linear Interpolation
• A New Look at Euler's Theorem for Polyhedra
• Lectures on Polytopes
• The Error in Linear Interpolation at the Vertices of a Simplex
• Pseudotriangulations from Surfaces and a Novel Type of Edge Flip
• Conforming Delaunay triangulations in 3D
• Power Diagrams: Properties, Algorithms and Applications
• Mesh generation for domains with small angles

This page was built for publication: General-dimensional constrained Delaunay and constrained regular triangulations. I: Combinatorial properties