Complexity of Delaunay Triangulation for Points on Lower-dimensional~Polyhedra

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 , Inria Saclay - Ile de France
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 O(n^(d-1)/p))$. For all p between 2 and d-1, this improves on the well-known worst-case bound of $O(n^ceil(d/2))$.
Type de document :
Communication dans un congrès
18th ACM-SIAM Symposium on Discrete Algorithms, Jan 2007, New Orleans, United States. pp.1106--1113, 2007
Liste complète des métadonnées

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

https://hal.inria.fr/inria-00182835
Contributeur : Olivier Devillers <>
Soumis le : jeudi 8 novembre 2007 - 10:11:20
Dernière modification le : mercredi 17 octobre 2018 - 19:54:01
Document(s) archivé(s) le : vendredi 25 novembre 2016 - 19:24:51

Fichier

hal.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : inria-00182835, version 2

Citation

Nina Amenta, Dominique Attali, Olivier Devillers. Complexity of Delaunay Triangulation for Points on Lower-dimensional~Polyhedra. 18th ACM-SIAM Symposium on Discrete Algorithms, Jan 2007, New Orleans, United States. pp.1106--1113, 2007. 〈inria-00182835v2〉

Partager

Métriques

Consultations de la notice

553

Téléchargements de fichiers

187