# 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 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

https://hal.inria.fr/inria-00182835
Contributor : Olivier Devillers <>
Submitted on : Monday, October 29, 2007 - 10:25:57 AM
Last modification on : Friday, September 6, 2019 - 3:00:06 PM
Long-term archiving on : Monday, September 24, 2012 - 2:41:20 PM

### File

camera.pdf
Files produced by the author(s)

### Identifiers

• HAL Id : inria-00182835, version 1

### Citation

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

Record views