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 <>
Submitted on : Thursday, July 22, 2021 - 4:12:32 PM
Last modification on : Saturday, July 24, 2021 - 3:47:13 AM


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