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.
Type de document :
Rapport
[Research Report] RR-6522, -; INRIA. 2008
Liste complète des métadonnées

Littérature citée [15 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/inria-00277899
Contributeur : Olivier Devillers <>
Soumis le : mardi 13 mai 2008 - 10:14:29
Dernière modification le : jeudi 11 janvier 2018 - 16:22:46
Document(s) archivé(s) le : vendredi 25 novembre 2016 - 22:00:38

Fichier

RR-6522.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • 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〉

Partager

Métriques

Consultations de la notice

345

Téléchargements de fichiers

131