Asymptotics for Euclidean minimal spanning trees on random points

Speaker : Bharath Roy Choudhury
Inria
Date: 19/02/2020
Time: 11:00 am - 12:00 pm
Location: Paris-Rennes Room (EIT Digital)

Abstract

I will present the main ideas of the paper “Asymptotics for Euclidean minimal spanning trees on random points” by David Aldous and J. Michael Steele. In this paper, the authors define Euclidean minimal spanning forest on a Poisson point process using a greedy algorithm. They compute the expectation of functionals on this minimal spanning forest such as the degree of a vertex, the sum of the d-th power of edge lengths incident at a vertex (where d is the dimension of the Euclidean space on which Poisson point lie). Their computations are based on the approximation of the Poisson point process with a scaled and shifted uniform i.i.d. random points on the unit cube. The conjectures posed by the authors in this paper were partially resolved later and stimulated further research.

The slides.