28559 articles – 22057 Notices  [english version]

inria-00098300, version 2

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

Nina Amenta () a, 1, Dominique Attali () b, 2, Olivier Devillers () c, 3

N° RR-5986 (2006)

Résumé : 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.

  • a –  University of California at Davis
  • b –  CNRS
  • c –  INRIA
  • 1 :  Visualization and Graphics Research Group.
  • University of California at Davis
  • 2 :  Laboratoire des images et des signaux (LIS)
  • CNRS : UMR5083 – Institut National Polytechnique de Grenoble (INPG) – Université Joseph Fourier - Grenoble I
  • 3 :  GEOMETRICA (INRIA Sophia Antipolis)
  • INRIA
  • Domaine : Informatique/Géométrie algorithmique
  • Mots-clés : Delaunay – reconstruction – surface sampling
  • Référence interne : RR-5986
  • Commentaire : This research was initiated at the McGill-INRIAWorkshop on Computational Geometry in Computer Graphics – February 2006 – co-organized by H. Everett – S. Lazard – and S. Whitesides – and held at the Bellairs Research Institute of McGill University.
  • Versions disponibles :  v1 (26-09-2006) v2 (26-09-2006)
 
  • inria-00098300, version 2
  • http://hal.inria.fr/inria-00098300
  • oai:hal.inria.fr:inria-00098300
  • Contributeur : Rapport De Recherche Inria <>
  • Soumis le : Mardi 26 Septembre 2006, 11:12:11
  • Dernière modification le : Jeudi 14 Janvier 2010, 17:09:58