This project aims to develop the probabilistic analysis of several problems of Euclidean combinatorial optimization while principally focusing on concrete questions involving minimal cost paths, minimum spanning trees, Steiner trees, and minimal cost matchings. One critical line of investigation concerns the possibility of a central limit theorem for subadditive Euclidean functionals, especially for the length of the minimal spanning tree of a random sample. Connections between this problem and the theory of continuum percolation are strong, and progress in either of these two areas can be expected to have useful impact on the other. The overall significance of the project comes in part from the fact that probabilistic methods in the theory of algorithms have already led to a number of well acknowledged computational breakthroughs, and additionally, from the observation that computational problems have many sustained interactions with topics that are central to probability theory, like the theory of martingale inequalities, Gaussian processes, and empirical processes. This project aims to develop the applications of probabilistic methods to problems that are of concern to computer scientists, operations researchers, and others who engage questions of optimization of discrete systems. The particular feature of the problems of main interest to the proposal is that of a close connection between geometry, optimization, and natural probability models for random sets of points in Euclidean space.
