Probabilistic Analysis of Large Complex Geometric Structures

Lehigh University, Bethlehem PA

Investigators

Abstract

Many questions arising in stochastic geometry and applied probability, as well as questions arising in networks, spatial statistics, and statistical mechanics, may be understood in terms of the behavior of large random geometric structures, where `large' means that the randomness involves a growing number of random variables. `Geometric' means that the problems depend heavily on the geometry of the underlying space. Problems involving these complex structures involve understanding the behavior of sums of spatially dependent terms having short range interactions, but complicated long range dependence. Problems of interest in discrete stochastic geometry involve functionals of convex hulls of i.i.d. samples, asymptotic quantization error, the limit behavior of maximal points, and the limit behavior of generalized tessellations in Euclidean space. Problems of interest involving spatial data include dimension estimation of non-linear data clouds embedded in a high dimensional Euclidean space, estimation of entropy, estimation of surface and volume integrals, as well as establishing minimal cost networks for data transmission and energy scaling laws. In each case, one seeks to quantify the `mean' or average behavior of functionals arising in these problems. A chief goal is to show that sums of spatially dependent terms behave as though they were sums of independent identically distributed random variables. One thus wants to show that such sums satisfy laws of large numbers, that they have asymptotically a normal distribution, and that the random point measures defined by these sums satisfy functional central limit theorems, that is to say show their scaling behavior is understood in terms of Brownian sheets. This project aims to solve problems in geometric probability which are of interest to researchers in both industry and academia. Examples include the following: (i) given an unknown object or body (such as an infarction in the human body or an underground deposit of oil) how can we use effectively use random probes of the object to find reliable estimators of its surface area and volume? (ii) given a huge amount of spatial data, how do we use only the interpoint distances of the data to determine intrinsic properties of the data, including its intrinsic dimension? (iii) given a network such as the world wide web, how does one best find ways to efficiently transmit and route information through it, minimizing cost and travel time? Similarly, given a communication network, how does one optimally place transmitters to maximize coverage? (iv) given any complex network, including airline and other transportation networks, how does one efficiently route vehicles to maximize revenue? The goal of this project is to develop theoretical tools to solve these and related problems and to develop efficient algorithms of use in industry.