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.
Document type :
Reports
Complete list of metadatas

Cited literature [19 references]  Display  Hide  Download

https://hal.inria.fr/inria-00098300
Contributor : Rapport de Recherche Inria <>
Submitted on : Tuesday, September 26, 2006 - 11:12:11 AM
Last modification on : Friday, September 6, 2019 - 3:00:06 PM
Long-term archiving on : Monday, September 20, 2010 - 5:02:20 PM

Identifiers

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

Share

Metrics

Record views

350

Files downloads

518