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 Delaunay triangulation 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)$ [Attali et al.]. Using this result, we prove that when points are Poisson distributed on a surface under the same hypothesis, with intensity $\lambda$, the expected size is $O(\lambda \log^2 \lambda)$.
Document type :
Reports
Complete list of metadatas

Cited literature [10 references]  Display  Hide  Download


https://hal.inria.fr/hal-01962631
Contributor : Olivier Devillers <>
Submitted on : Thursday, December 20, 2018 - 5:07:42 PM
Last modification on : Monday, November 4, 2019 - 8:12:05 AM

Files

RR-9239.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-01962631, version 1

Citation

Olivier Devillers, Charles Duménil. A Poisson sample of a smooth surface is a good sample. [Research Report] RR-9239, INRIA Nancy. 2018, pp.8. ⟨hal-01962631⟩

Share

Metrics

Record views

75

Files downloads

64