Random geometric graph diameter in the unit ball Conference Paper uri icon

abstract

  • The unit ball random geometric graph G=G Pd(, n) has as its vertices n points distributed independently and uniformly in the unit ball in , with two vertices adjacent if and only if their p-distance is at most . Like its cousin the Erdos-Renyi random graph, G has a connectivity threshold: an asymptotic value for in terms of n, above which G is connected and below which G is disconnected. In the connected zone we determine upper and lower bounds for the graph diameter of G. Specifically, almost always, diam p(B)(1-o(1))/ diam(G) diam p(B)(1+O((ln ln n/ln,n) 1/d))/, where diam p(B) is the p-diameter of the unit ball B. We employ a combination of methods from probabilistic combinatorics and stochastic geometry. Springer 2007.

published proceedings

  • ALGORITHMICA

author list (cited authors)

  • Ellis, R. B., Martin, J. L., & Yan, C.

citation count

  • 26

complete list of authors

  • Ellis, Robert B||Martin, Jeremy L||Yan, Catherine

publication date

  • April 2007