Stochastic Analysis of Empty-Region Graphs - INRIA - Institut National de Recherche en Informatique et en Automatique Accéder directement au contenu
Communication Dans Un Congrès Année : 2021

Stochastic Analysis of Empty-Region Graphs

Résumé

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.
Fichier principal
Vignette du fichier
paper12.pdf (1.54 Mo) Télécharger le fichier
Vignette du fichier
vignette.png (32.42 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Format : Figure, Image

Dates et versions

hal-03296186 , version 1 (22-07-2021)

Identifiants

  • HAL Id : hal-03296186 , version 1

Citer

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⟩
72 Consultations
54 Téléchargements

Partager

Gmail Facebook X LinkedIn More