Skip to Main content Skip to Navigation
Conference papers

Stochastic Analysis of Empty-Region Graphs

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 : Given a set of points $X$, an empty-region graph is a graph in which $p$, $q \in X$ are neighbors if some region defined by $(p, q)$ does not contain any point of $X$. We provide expected analyses of the degree of a point and the possibility of having far neighbors in such a graph when $X$ is a planar Poisson point process. Namely the expected degree of a point in the empty axis-alignedellipse graph for a Poisson point process of intensity $\lambda$ in the unit square is $\Theta(\ln\lambda)$. It is $\Theta(\ln\beta)$ if the ellipses are constrained to have an aspect ratio between 1 and $\beta>1$, and $\Theta(\beta)$ when the aspect ratio is constrained but ellipses are not axis-aligned.
Document type :
Conference papers
Complete list of metadata
Contributor : Olivier Devillers Connect in order to contact the contributor
Submitted on : Thursday, July 22, 2021 - 4:12:32 PM
Last modification on : Friday, February 4, 2022 - 9:00:13 AM
Long-term archiving on: : Saturday, October 23, 2021 - 7:02:13 PM


Files produced by the author(s)


  • HAL Id : hal-03296186, version 1



Olivier Devillers, Charles Duménil. Stochastic Analysis of Empty-Region Graphs. CCCG 2021 - 33rd Canadian Conference on Computational Geometry, Aug 2021, Halifax / Virtual, Canada. ⟨hal-03296186⟩



Record views


Files downloads