Theoretical Statistics and Mathematics Unit, ISI Delhi

Connectivity Threshold of Random Geometric Graphs with Cantor Distributed Vertices

by Antar Bandyopadhyay and Farkhondeh Sajadi

For connectivity of \emph{random geometric graphs}, where there is no density for underlying distribution of the vertices, we consider
$n$ i.i.d. \emph{Cantor} distributed points on $[0,1]$. We show that for this random geometric graph, the connectivity threshold $R_{n}$,
converges almost surely to a constant $1-2\phi$ where $0 < \phi < 1/2$,
which for standard Cantor distribution is $1/3$. We also show that
$\left\| R_n - \left(1 - 2 \phi \right) \right\|_1 \sim 2 \, C\left(\phi\right) \, n^{-1/d_{\phi}}$
where $C\left(\phi\right) > 0$ is a constant and $d_{\phi} := - {\log 2}/{\log \phi}$ is a the
\emph{Hausdorff dimension} of the generalized Cantor set with parameter $\phi$.

isid/ms/2012/06 [fulltext]

Click here to return to Preprints Page