Published 2007
| Version v1
Report
Random sampling of a cylinder yields a not so nasty Delaunay triangulation
Creators
Contributors
Others:
- Geometric computing (GEOMETRICA) ; INRIA Futurs ; Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre Inria d'Université Côte d'Azur (CRISAM) ; Institut National de Recherche en Informatique et en Automatique (Inria)
- Effective Geometric Algorithms for Surfaces and Visibility (VEGAS) ; INRIA Lorraine ; Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Laboratoire Lorrain de Recherche en Informatique et ses Applications (LORIA) ; Institut National de Recherche en Informatique et en Automatique (Inria)-Université Henri Poincaré - Nancy 1 (UHP)-Université Nancy 2-Institut National Polytechnique de Lorraine (INPL)-Centre National de la Recherche Scientifique (CNRS)-Université Henri Poincaré - Nancy 1 (UHP)-Université Nancy 2-Institut National Polytechnique de Lorraine (INPL)-Centre National de la Recherche Scientifique (CNRS)
- INRIA
Description
We prove that the expected size of the 3D Delaunay triangulation of n points evenly distributed on a cylinder is Theta(n log n). This shows that the n sqrt(n) behavior of the cylinder-example of Erickson is pathological.
Additional details
Identifiers
- URL
- https://inria.hal.science/inria-00179313
- URN
- urn:oai:HAL:inria-00179313v2
Origin repository
- Origin repository
- UNICA