A Poisson sample of a smooth surface is a good sample

Olivier Devillers 1 Charles Duménil 1
1 GAMBLE - Geometric Algorithms and Models Beyond the Linear and Euclidean realm
Inria Nancy - Grand Est, LORIA - ALGO - Department of Algorithms, Computation, Image and Geometry
Abstract : The complexity of the 3D-Delaunay triangulation (tetrahedralization) of n points distributed on a surface ranges from linear to quadratic. When the points are a deterministic good sample of a smooth compact generic surface, the size of the Delaunay triangulation is O(n log n). Using this result, we prove that when points are Poisson distributed on a surface under the same hypothesis, whose expected number of vertices is λ, the expected size is O(λ log^2 λ).
Document type :
Conference papers
Complete list of metadatas

Contributor : Charles Duménil <>
Submitted on : Wednesday, December 4, 2019 - 4:14:51 PM
Last modification on : Thursday, December 5, 2019 - 1:38:51 AM


  • HAL Id : hal-02394144, version 1



Olivier Devillers, Charles Duménil. A Poisson sample of a smooth surface is a good sample. EuroCG 2019, Feb 2019, Utrecht, Netherlands. ⟨hal-02394144⟩



Record views