Random Directional Nearest-Neighbour Graphs

Abstract

We look at a class of random spatial graphs constructed on random points (points of a Poisson process) in Euclidean space with edges defined by a geometrical rule based on proximity. Specifically, each point is joined by an edge to its nearest neighbour in a given direction specified by a cone. The unrestricted case is the ordinary nearest-neighbour graph; the restricted case is a version of the minimal directed spanning forest (MDSF) introduced by Bhatt & Roy. These graphs have been widely used for modelling networks with spatial content, such as in the communications sector, social networks, and transportation networks. The large-sample asymptotic behaviour of the total edge length of these graphs is our main interest. For the ordinary nearest-neighbour graph, the appropriate central limit theorem is due to Avram & Bertsimas. For the MDSF, the limit theory is known (Penrose & Wade) in two special cases, namely the 'south' and 'south-west' versions: here the limit is not normal, due to the presence of long edges near to the boundary. In this thesis, we will extend the limit theory to the case of general cones; depending on the parameters, the limit distribution may be normal, or the convolution of a normal distribution with a non-normal element due to boundary effects whose distribution can be characterized by a fixed-point equation.