 |
 |
 |
Journal articles
A tight bound for the Delaunay triangulation of points on a polyhedron
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$.
Cited literature [11 references]
https://hal.archives-ouvertes.fr/hal-00784900
Contributor : Dominique Attali Connect in order to contact the contributor
Submitted on : Monday, February 4, 2013 - 10:36:09 PM
Last modification on : Thursday, January 20, 2022 - 5:29:17 PM
Long-term archiving on: : Monday, June 17, 2013 - 7:10:42 PM
Contributor : Dominique Attali Connect in order to contact the contributor
Submitted on : Monday, February 4, 2013 - 10:36:09 PM
Last modification on : Thursday, January 20, 2022 - 5:29:17 PM
Long-term archiving on: : Monday, June 17, 2013 - 7:10:42 PM
Files
2012-dcg-size-delaunay.pdf
Files produced by the author(s)
