A Tight Bound for the Delaunay Triangulation of Points on a Polyhedron

Nina Amenta 1 Dominique Attali 2 Olivier Devillers 3
2 GIPSA-GPIG - GPIG
GIPSA-DIS - Département Images et Signal
3 GEOMETRICA - Geometric computing
CRISAM - Inria Sophia Antipolis - Méditerranée
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
Liste complète des métadonnées

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 : Sunday, November 25, 2018 - 2:28: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

459

Files downloads

180