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

Nina Amenta 1 Dominique Attali 2 Olivier Devillers 3
2 GIPSA-GPIG - GPIG
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
Liste complète des métadonnées

Cited literature [16 references]  Display  Hide  Download

https://hal.inria.fr/inria-00182835
Contributor : Olivier Devillers <>
Submitted on : Thursday, November 8, 2007 - 10:11:20 AM
Last modification on : Sunday, November 25, 2018 - 2:28:09 PM
Document(s) archivé(s) le : Friday, November 25, 2016 - 7:24:51 PM

File

hal.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : inria-00182835, version 2

Citation

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

Share

Metrics

Record views

679

Files downloads

212