Published 2006
| Version v1
Report
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)
- Laboratoire des images et des signaux (LIS) ; Université Joseph Fourier - Grenoble 1 (UJF)-Institut National Polytechnique de Grenoble (INPG)-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
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 of order n to the power (d-1)/p for p between 2 and d-1. This improves on the well-known worst-case bound of n to the power ceiling of d/2.
Abstract
This research was initiated at the McGill-INRIAWorkshop on Computational Geometry in Computer Graphics, February 2006, co-organized by H. Everett, S. Lazard, and S. Whitesides, and held at the Bellairs Research Institute of McGill University.Additional details
Identifiers
- URL
- https://inria.hal.science/inria-00098300
- URN
- urn:oai:HAL:inria-00098300v2
Origin repository
- Origin repository
- UNICA