AF: Small: New Directions in Computational Geometry

AF：小：计算几何的新方向

• 批准号: 1016250
• 负责人: Bernard Chazelle
• 金额: $ 34.8万
• 依托单位: Princeton University
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2010
• 资助国家: 美国
• 起止时间: 2010-09-01 至 2015-08-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1016250&HistoricalAwards=false
• 关键词: AF; Small; New; Directions; Computational

This award seeks progress in new areas of computational geometry: specifically, collective behavior, sublinearity, hereditary structures, and low-entropy geometric algorithms. Recent work on multiagent agreement systems has revealed the great potential of a geometric approach to the subject. A new generating function, the "total s-energy", shows considerable promise for the study of consensus. A thorough investigation of this new device is the starting point of this project. Geometric data tends to capture a vast amount of coherence and hence little entropy. The second part of this project looks at four instances of this phenomenon: Markov sources, hereditary complexity, sublinear computing, and self-improving geometric algorithms. In the first case, the data is generated by a Markov chain; in the second, it is presented within a larger structure that is given explicitly; in the third, the data is only accessible in limited amounts through random sampling; in the fourth, it comes from an unknown memoryless low-entropy distribution. In all cases, the objective is the same: to go beyond worst-case analysis and make room for a more realistic analytical framework.

该奖项旨在寻求计算几何新领域的进展：具体而言，集体行为、次线性、遗传结构和低熵几何算法。 最近关于多智能体协议系统的工作揭示了几何方法对该主题的巨大潜力。 一个新的生成函数，“总 s 能量”，为共识研究展现了巨大的前景。 对这个新设备的彻底调查是这个项目的起点。 几何数据往往会捕获大量的相干性，因此熵很少。 该项目的第二部分着眼于这种现象的四个实例：马尔可夫源、遗传复杂性、次线性计算和自我改进的几何算法。 第一种情况，数据是由马尔可夫链生成的；在第二个中，它是在一个明确给出的更大的结构中呈现的；第三，只能通过随机抽样获取有限数量的数据；第四个，它来自未知的无记忆低熵分布。 在所有情况下，目标都是相同的：超越最坏情况分析，为更现实的分析框架腾出空间。