Skip to Main content Skip to Navigation
Reports

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^((d-k+1)/p)), where k = ceil(d+1)/(p+1)$. This bound is tight, and improves on the prior upper bound for most values of p.
Document type :
Reports
Complete list of metadatas

Cited literature [15 references]  Display  Hide  Download

https://hal.inria.fr/inria-00277899
Contributor : Olivier Devillers <>
Submitted on : Tuesday, May 13, 2008 - 10:14:29 AM
Last modification on : Thursday, July 9, 2020 - 5:02:09 PM
Document(s) archivé(s) le : Friday, November 25, 2016 - 10:00:38 PM

File

RR-6522.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : inria-00277899, version 2

Citation

Nina Amenta, Dominique Attali, Olivier Devillers. A Tight Bound for the Delaunay Triangulation of Points on a Polyhedron. [Research Report] RR-6522, -; INRIA. 2008. ⟨inria-00277899v2⟩

Share

Metrics

Record views

541

Files downloads

701