Mathematics – Combinatorics
Scientific paper
2005-01-14
Algorithmica 47, no. 4 (2007), 421-438
Mathematics
Combinatorics
17 pages, 4 figures; exposition revised substantially, particularly in Sections 3 and 5
Scientific paper
The unit ball random geometric graph $G=G^d_p(\lambda,n)$ has as its vertices $n$ points distributed independently and uniformly in the $d$-dimensional unit ball, with two vertices adjacent if and only if their $l_p$-distance is at most $\lambda$. Like its cousin the Erdos-Renyi random graph, $G$ has a connectivity threshold: an asymptotic value for $\lambda$ in terms of $n$, above which $G$ is connected and below which $G$ is disconnected (and in fact has isolated vertices in most cases). In the connected zone, we determine upper and lower bounds for the graph diameter of $G$. Specifically, almost always, $\diam_p(\mathbf{B})(1-o(1))/\lambda \leq \diam(G) \leq \diam_p(\mathbf{B})(1+O((\ln \ln n/\ln n)^{1/d}))/\lambda$, where $\diam_p(\mathbf{B})$ is the $\ell_p$-diameter of the unit ball $\mathbf{B}$. We employ a combination of methods from probabilistic combinatorics and stochastic geometry.
Ellis Robert B.
Martin Jeremy L.
Yan Catherine
No associations
LandOfFree
Random Geometric Graph Diameter in the Unit Ball does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Random Geometric Graph Diameter in the Unit Ball, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Random Geometric Graph Diameter in the Unit Ball will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-87961