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

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 λ).

Mots clés: Poisson sample; Surface; Computational geometry; Delaunay triangulation

Domaines: Informatique [cs]; Géométrie algorithmique [cs.CG]

Olivier Devillers, Charles Duménil. A Poisson sample of a smooth surface is a good sample. EuroCG 2019 - 35th European Workshop on Computational Geometry, Mar 2019, Utrecht, Netherlands. ⟨hal-02394144⟩