Skip to Main content Skip to Navigation
Reports

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

Nina Amenta 1 Dominique Attali 2 Olivier Devillers 3
1 Visualization and Graphics Research Group.
2 LIS - Laboratoire des images et des signaux
3 GEOMETRICA - Geometric computing
CRISAM - Inria Sophia Antipolis - Méditerranée
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.
keyword : Delaunay reconstruction surface sampling
Document type :
Reports
Complete list of metadata
https://hal.inria.fr/inria-00098300
Contributor : Olivier Devillers <>
Submitted on : Monday, September 25, 2006 - 2:53:26 PM
Last modification on : Monday, November 16, 2020 - 2:10:03 PM
Long-term archiving on: : Monday, April 5, 2010 - 11:15:29 PM

Files

Vignette du document
RR.pdf

Identifiers

  • HAL Id : inria-00098300, version 1

Citation

Nina Amenta, Dominique Attali, Olivier Devillers. Complexity of Delaunay triangulation for points on lower-dimensional~polyhedra. [Research Report] 2006, pp.12. ⟨inria-00098300v1⟩

Export

BibTeX TEI DC DCterms EndNote

Share

Metrics

Record views

10

Files downloads

5

 

Contact                    Legal Notice                    Personal Data