HAL will be down for maintenance from Friday, June 10 at 4pm through Monday, June 13 at 9am. More information
Skip to Main content Skip to Navigation
Reports

Random sampling of a cylinder yields a not so nasty Delaunay triangulation

Olivier Devillers 1 Xavier Goaoc 2
1 GEOMETRICA - Geometric computing
INRIA Futurs, CRISAM - Inria Sophia Antipolis - Méditerranée
2 VEGAS - Effective Geometric Algorithms for Surfaces and Visibility
INRIA Lorraine, LORIA - Laboratoire Lorrain de Recherche en Informatique et ses Applications
Abstract : 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.
Document type :
Reports
Complete list of metadata

Cited literature [16 references]  Display  Hide  Download

https://hal.inria.fr/inria-00179313
Contributor : Olivier Devillers Connect in order to contact the contributor
Submitted on : Monday, October 22, 2007 - 11:16:02 AM
Last modification on : Friday, February 26, 2021 - 3:28:08 PM
Long-term archiving on: : Friday, November 25, 2016 - 6:53:47 PM

File

RR.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : inria-00179313, version 2

Collections

Citation

Olivier Devillers, Xavier Goaoc. Random sampling of a cylinder yields a not so nasty Delaunay triangulation. [Research Report] RR-6323, INRIA. 2007, pp.10. ⟨inria-00179313v2⟩

Share

Metrics

Record views

151

Files downloads

337