Probabilistic Analysis of Large Complex Geometric Structures

大型复杂几何结构的概率分析

• 批准号: 1106619
• 负责人: Joseph Yukich
• 金额: $ 19.5万
• 依托单位: Lehigh University
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 2011
• 资助国家: 美国
• 起止时间: 2011-08-15 至 2014-07-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1106619&HistoricalAwards=false
• 关键词: Probabilistic; Analysis; Large; Complex; Geometric

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 maximizerevenue? 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.

随机几何和应用概率中出现的许多问题，以及网络、空间统计和统计力学中出现的问题，可以用大型随机几何结构的行为来理解，其中“大”意味着随机性涉及越来越多的随机变量。 “几何”意味着问题在很大程度上取决于底层空间的几何形状。 涉及这些复杂结构的问题涉及理解具有短程相互作用但复杂的长程依赖性的空间相关项之和的行为。离散随机几何中感兴趣的问题涉及独立同分布的凸包泛函。样本、渐近量化误差、极大点的极限行为以及欧几里得空间中广义镶嵌的极限行为。涉及空间数据的感兴趣的问题包括嵌入高维欧几里得空间中的非线性数据云的维度估计、熵的估计、表面和体积积分的估计，以及建立用于数据传输和能量缩放定律的最小成本网络。在每种情况下，人们都试图量化这些问题中出现的泛函的“平均”或平均行为。 主要目标是证明空间相关项的总和的行为就像独立同分布随机变量的总和一样。 因此，人们想要证明这些和满足大数定律，它们具有渐近正态分布，并且由这些和定义的随机点测度满足函数中心极限定理，也就是说表明它们的标度行为可以用布朗表来理解。该项目旨在解决工业界和学术界研究人员都感兴趣的几何概率问题。示例如下：（i）给定一个未知的物体或身体（例如人体内的梗塞或地下石油沉积物），我们如何有效地使用物体的随机探针来找到其表面积和体积的可靠估计器？ (ii) 给定大量空间数据，我们如何仅使用数据的点间距来确定数据的内在属性，包括其内在维度？ (iii) 给定一个像万维网这样的网络，如何最好地找到通过它有效传输和路由信息的方法，最大限度地减少成本和旅行时间？同样，给定一个通信网络，如何最佳地放置发射器以最大化覆盖范围？（iv）给定任何复杂的网络，包括航空公司和其他运输网络，如何有效地路由车辆以最大化收入？ 该项目的目标是开发理论工具来解决这些及相关问题，并开发在工业中使用的有效算法。