Skip to Main content Skip to Navigation
Conference papers

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

Nina Amenta 1 Dominique Attali 2 Olivier Devillers 3
2 GIPSA-GPIG - GIPSA - Géométrie, Perception, Images, Geste
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))$.
Document type :
Conference papers
Complete list of metadata

Cited literature [16 references]  Display  Hide  Download
Contributor : Olivier Devillers Connect in order to contact the contributor
Submitted on : Thursday, November 8, 2007 - 10:11:20 AM
Last modification on : Thursday, January 20, 2022 - 5:30:37 PM
Long-term archiving on: : Friday, November 25, 2016 - 7:24:51 PM


Files produced by the author(s)


  • HAL Id : inria-00182835, version 2



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



Les métriques sont temporairement indisponibles