The Design and Analysis of Geometric Algorithms

几何算法的设计与分析

• 批准号: 9301254
• 负责人: Bernard Chazelle
• 金额: $ 31.62万
• 依托单位: Princeton University
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 1993
• 资助国家: 美国
• 起止时间: 1993-08-01 至 1997-01-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=9301254&HistoricalAwards=false
• 关键词: Design; Analysis; Geometric; Algorithms

The project investigates problems within three broad areas of computational geometry: (1) design and implementation of efficient and robust geometric primitives, (2) algorithmic complexity of multidimensional searching and (3) mathematical tools (e.g. discrepancy theory) for randomized (and derandomized) geometric algorithms. These areas cover the spectrum from practical considerations which arise when implementing and debugging geometric algorithms to theoretical questions arising in algorithm design and lower bound proofs. Tools continue to be built which can ultimately be used to produce and share geometric software.

该项目研究计算几何的三个广泛领域中的问题：(1)高效和健壮的几何原语的设计和实现；(2)多维搜索的算法复杂性；(3)随机（和非随机）几何算法的数学工具（例如差异理论）。这些领域涵盖了从实现和调试几何算法时出现的实际考虑到算法设计和下界证明中出现的理论问题的范围。工具继续被构建，最终可以用于生产和共享几何软件。