Published 2008
| Version v1
Report
A Tight Bound for the Delaunay Triangulation of Points on a Polyhedron
Contributors
Others:
- Visualization and Graphics Research Group. ; University of California [Davis] (UC Davis) ; University of California (UC)-University of California (UC)
- GIPSA - Géométrie, Perception, Images, Geste (GIPSA-GPIG) ; Département Images et Signal (GIPSA-DIS) ; Grenoble Images Parole Signal Automatique (GIPSA-lab) ; Université Pierre Mendès France - Grenoble 2 (UPMF)-Université Stendhal - Grenoble 3-Université Joseph Fourier - Grenoble 1 (UJF)-Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP)-Centre National de la Recherche Scientifique (CNRS)-Université Pierre Mendès France - Grenoble 2 (UPMF)-Université Stendhal - Grenoble 3-Université Joseph Fourier - Grenoble 1 (UJF)-Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP)-Centre National de la Recherche Scientifique (CNRS)-Grenoble Images Parole Signal Automatique (GIPSA-lab) ; Université Pierre Mendès France - Grenoble 2 (UPMF)-Université Stendhal - Grenoble 3-Université Joseph Fourier - Grenoble 1 (UJF)-Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP)-Centre National de la Recherche Scientifique (CNRS)-Université Pierre Mendès France - Grenoble 2 (UPMF)-Université Stendhal - Grenoble 3-Université Joseph Fourier - Grenoble 1 (UJF)-Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP)-Centre National de la Recherche Scientifique (CNRS)
- Geometric computing (GEOMETRICA) ; Centre Inria d'Université Côte d'Azur (CRISAM) ; Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)
- INRIA
- ANR-07-BLAN-0319,Triangles,New challenges in triangulations(2007)
Description
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^((d-k+1)/p)), where k = ceil(d+1)/(p+1)$. This bound is tight, and improves on the prior upper bound for most values of p.
Additional details
Identifiers
- URL
- https://inria.hal.science/inria-00277899
- URN
- urn:oai:HAL:inria-00277899v2
Origin repository
- Origin repository
- UNICA