Skip to Main content Skip to Navigation
Journal articles

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

Nina Amenta 1 Dominique Attali 2, * Olivier Devillers 3
* Corresponding author
3 GEOMETRICA - Geometric computing
CRISAM - Inria Sophia Antipolis - Méditerranée , Inria Saclay - Ile de France
Abstract : We show that the Delaunay triangulation of a set of $n$ points distributed nearly uniformly on a $p$-dimensional polyhedron (not necessarily convex) in $d$-dimensional Euclidean space is $O(n^{\frac{d-k+1}{p}})$, where $k = \lceil \frac{d+1}{p+1} \rceil$. This bound is tight in the worst case, and improves on the prior upper bound for most values of $p$.
Document type :
Journal articles
Complete list of metadatas

Cited literature [11 references]  Display  Hide  Download
Contributor : Dominique Attali <>
Submitted on : Monday, February 4, 2013 - 10:36:09 PM
Last modification on : Thursday, November 19, 2020 - 1:01:02 PM
Long-term archiving on: : Monday, June 17, 2013 - 7:10:42 PM


Files produced by the author(s)



Nina Amenta, Dominique Attali, Olivier Devillers. A tight bound for the Delaunay triangulation of points on a polyhedron. Discrete and Computational Geometry, Springer Verlag, 2012, 48 (1), pp.19-38. ⟨10.1007/s00454-012-9415-7⟩. ⟨hal-00784900⟩



Record views


Files downloads