Published January 7, 2007
| Version v1
Conference paper
Complexity of Delaunay Triangulation for Points on Lower-dimensional~Polyhedra
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)-Centre Inria de Saclay ; Institut National de Recherche en Informatique et en Automatique (Inria)
Description
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))$.
Abstract
Equipe GPIG de GIPSA-labAbstract
International audienceAdditional details
Identifiers
- URL
- https://inria.hal.science/inria-00182835
- URN
- urn:oai:HAL:inria-00182835v2
Origin repository
- Origin repository
- UNICA