A tight bound for the Delaunay triangulation of points on a polyhedron

DOI10.1007/s00454-012-9415-7zbMath1254.51010OpenAlexW2078340633MaRDI QIDQ443906

Olivier Devillers, Nina Amenta, Dominique Attali

Publication date: 13 August 2012

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

Full work available at URL: https://doi.org/10.1007/s00454-012-9415-7

zbMATH Keywords

samplingcomplexityupper boundpolyhedronDelaunay triangulationhigh dimensionannular medial axis

Mathematics Subject Classification ID

Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Polyhedra and polytopes; regular figures, division of spaces (51M20) Mesh generation, refinement, and adaptive methods for ordinary differential equations (65L50)

Related Items

RDELA -- a Delaunay-triangulation-based, location and covariance estimator with high breakdown point

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• A linear bound on the complexity of the Delaunay triangulation of points on polyhedral surfaces
• Nice point sets can have nasty Delaunay triangulations
• On the average complexity of 3D-Voronoi diagrams of random points on convex polytopes
• The Probability That a Numerical Analysis Problem is Difficult
• The probabilistic complexity of the Voronoi diagram of points on a polyhedron
• Complexity of the delaunay triangulation of points on surfaces the smooth case
• The maximum numbers of faces of a convex polytope