Paper Info
Title
On the distribution of typical shortest-path lengths in connected random geometric graphs
Abstract
Stationary point processes in 驴2 with two different types of points, say H and L, are considered where the points are located on the edge set G of a random geometric graph, which is assumed to be stationary and connected. Examples include the classical Poisson---Voronoi tessellation with bounded and convex cells, aggregate Voronoi tessellations induced by two (or more) independent Poisson processes whose cells can be nonconvex, and so-called β-skeletons being subgraphs of Poisson---Delaunay triangulations. The length of the shortest path along G from a point of type H to its closest neighbor of type L is investigated. Two different meanings of "closeness" are considered: either with respect to the Euclidean distance (e-closeness) or in a graph-theoretic sense, i.e., along the edges of G (g-closeness). For both scenarios, comparability and monotonicity properties of the corresponding typical shortest-path lengths C e驴 and C g驴 are analyzed. Furthermore, extending the results which have recently been derived for C e驴, we show that the distribution of C g驴 converges to simple parametric limit distributions if the edge set G becomes unboundedly sparse or dense, i.e., a scaling factor 驴 converges to zero and infinity, respectively.
Year
DOI
Venue
2012
10.1007/s11134-012-9276-z
Queueing Syst.
Keywords
Field
DocType
Point process,Aggregate tessellation,β,-skeleton,Shortest path,Palm mark distribution,Stochastic monotonicity,Scaling limit,60D05,60G55,60F99,90B15
Discrete mathematics,Combinatorics,Scaling limit,Shortest path problem,Point process,Regular polygon,Stationary point,Voronoi diagram,Random geometric graph,Mathematics,Bounded function
Journal
Volume
Issue
ISSN
71
1-2
0257-0130
Citations 
PageRank 
References 
2
0.64
1
Authors
4
Name
Order
Citations
PageRank
D. Neuhäuser131.02
C. Hirsch284.31
C. Gloaguen3235.25
V. Schmidt481.87