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.
https://hal.inria.fr/inria-00179313
Contributor : Olivier Devillers <>
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
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⟩