On random points in the unit disk
Academic Article
Overview
Identity
Additional Document Info
Other
View All
Overview
abstract
Let n be a positive integer and > 0 a real number. Let V n 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 V n, 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 = cln n/n and let X be the number of isolated points in G(, n). We prove that almost always X n 1-c2 when 0 c < 1. It is known that if = (ln n + (n))/n where (n) , then G(, n) is connected. By extending a method of Penrose, we show that under the same condition on , there exists a constant K such that the diameter of G(, n) is bounded above by K 2/. Furthermore, with a new geometric construction, we show that when = cln n/n and 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.
