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
1 Visualization and Graphics Research Group.
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 metadatas

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 : Thursday, November 19, 2020 - 1:01:01 PM
Long-term archiving on: : Friday, November 25, 2016 - 7:24:51 PM

File

Vignette du document
hal.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : inria-00182835, version 2

Collections

CNRS | INRIA | GIPSA-GPIG | GIPSA-DIS | GIPSA | UGA

Citation

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⟩

Export

BibTeX TEI DC DCterms EndNote

Share

Metrics

Record views

866

Files downloads

880