On random points in the unit disk
Robert B. Ellis, Xing‐De Jia, Catherine Huafei Yan · Random Structures and Algorithms · 2005
Abstract Let n be a positive integer and λ > 0 a real number. Let Vn be a set of n points in the unit disk selected uniformly and independently at random. Define G(λ, n) to be the graph with vertex set Vn, in which two vertices are adjacent if and only if their Euclidean distance is at most λ. We call this graph a unit disk random graph. Let $\lambda = c \sqrt {\ln n/n}$ and let X be the number of isolated points in G(λ, n). We prove that almost always X ∼ n when 0 ≤ c 2.26164 …, the diameter of G(λ, n) is bounded by (4 + o(1))/λ; and we modify this construction to yield a function c(δ) > 0 such that the diameter is at most 2(1 + δ + o(1))/λ when c > c(δ). © 2005 Wiley Periodicals, Inc. Random Struct. Alg., 2006