Discrete Mathematics & Theoretical Computer Science, Vol 15, No 2 (2013)

Font Size:  Small  Medium  Large

Connectivity for line-of-sight networks in higher dimensions

Luc Devroye, Linda Farczadi


Let $T$ be a $d$-dimensional toroidal grid of $n^d$ points. For a given range parameter $\omega$, and a positive integer $k \leq d$, we say that two points in $T$ are mutually visible if they differ in at most $k$ coordinates and are a distance at most $\omega$ apart, where distance is measured using the $\ell_p$ norm. We obtain a random $d$-dimensional line-of-sight graph $G$ by placing a node at each point in $T$ independently with some fixed probability $p^*$ and connecting all pairs of mutually visible nodes. We prove an asymptotically tight connectivity result for this random graph.

Full Text: PDF PostScript