Complexity of Delaunay triangulation for points on lower-dimensional~polyhedra

Abstract : We show that the Delaunay triangulation of a set of points distributed nearly uniformly on a polyhedron (not necessarily convex) of dimension p in d-dimensional space is of order n to the power (d-1)/p for p between 2 and d-1. This improves on the well-known worst-case bound of n to the power ceiling of d/2.
Type de document :
Rapport
[Research Report] RR-5986, INRIA. 2006, pp.12
Liste complète des métadonnées

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

https://hal.inria.fr/inria-00098300
Contributeur : Rapport de Recherche Inria <>
Soumis le : mardi 26 septembre 2006 - 11:12:11
Dernière modification le : samedi 27 janvier 2018 - 01:30:43
Document(s) archivé(s) le : lundi 20 septembre 2010 - 17:02:20

Fichiers

Identifiants

  • HAL Id : inria-00098300, version 2

Collections

Citation

Nina Amenta, Dominique Attali, Olivier Devillers. Complexity of Delaunay triangulation for points on lower-dimensional~polyhedra. [Research Report] RR-5986, INRIA. 2006, pp.12. 〈inria-00098300v2〉

Partager

Métriques

Consultations de la notice

291

Téléchargements de fichiers

160