HAL will be down for maintenance from Friday, June 10 at 4pm through Monday, June 13 at 9am. More information
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⟩



Record views


Files downloads