Published 2012
| Version v1
Journal article
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 - Architecture, Géométrie, Perception, Images, Gestes (GIPSA-AGPIG) ; 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)-Centre Inria de Saclay ; Institut National de Recherche en Informatique et en Automatique (Inria)
- European Project: 255827,EC:FP7:ICT,FP7-ICT-2009-C,CG LEARNING(2010)
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^{\frac{d-k+1}{p}})$, where $k = \lceil \frac{d+1}{p+1} \rceil$. This bound is tight in the worst case, and improves on the prior upper bound for most values of $p$.
Abstract
International audienceAdditional details
Identifiers
- URL
- https://hal.science/hal-00784900
- URN
- urn:oai:HAL:hal-00784900v1
Origin repository
- Origin repository
- UNICA