G(n, r): n points in unit square; connect pairs within radius r
Graph (color = connected component)
Component size distribution
r_c = √(ln n / πn) ≈ ? | r/r_c = ? | Largest component: ? nodes | Connected: ?
The random geometric graph (RGG) G(n,r) places n points uniformly at random in [0,1]², then connects every pair within Euclidean distance r. This models wireless sensor networks, social proximity, and spatial epidemics.
Sharp threshold (Penrose 1997): The graph transitions from disconnected to connected at r_c = √(ln n / πn). More precisely: if r = √((ln n + c)/πn), then P(connected) → e^{−2e^{−c}} as n→∞. The phase transition is sharp — the window is O(1/n).
The transition is driven by isolated vertices: connectivity fails iff there exists an isolated node, and the last isolated node disappears at r_c. This is the analogue of Erdős-Rényi's connectivity threshold, but with geometric constraints — edges are spatially correlated.
Below r_c: many small disconnected components. Above r_c: a giant component spanning nearly all nodes. The transition also coincides with the appearance of a giant clique-like structure.