Published in

Springer (part of Springer Nature), Discrete & Computational Geometry, 1(48), p. 19-38

DOI: 10.1007/s00454-012-9415-7

Links

Tools

Export citation

Search in Google Scholar

A Tight Bound for the Delaunay Triangulation of Points on a Polyhedron

Journal article published in 2008 by Nina Amenta, Dominique Attali, Olivier Devillers ORCID
This paper is available in a repository.
This paper is available in a repository.

Full text: Download

Green circle
Preprint: archiving allowed
Upload
Green circle
Postprint: archiving allowed
Upload
Red circle
Published version: archiving forbidden
Policy details
Data provided by SHERPA/RoMEO

Abstract

We show that the Delaunay triangulation of a set of $n$ points distributed nearly uniformly on a $p$-dimensional polyhedron (not necessarily convex) in $d$-dimensional Euclidean space is $O(n^{\frac{d-k+1}{p}})$, where $k = ⌈ \frac{d+1}{p+1} ⌉$. This bound is tight in the worst case, and improves on the prior upper bound for most values of $p$.