New Directions in Geometric Algorithm Design

几何算法设计的新方向

• 批准号: 0306283
• 负责人: David Dobkin
• 金额: $ 48万
• 依托单位: Princeton University
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 2003
• 资助国家: 美国
• 起止时间: 2003-08-01 至 2007-07-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0306283&HistoricalAwards=false
• 关键词: New; Directions; Geometric; Algorithm; Design

Special Abstract for 0306283 (Dobkin and Chazelle, Princeton U, Title: New Directions in Geometric Algorithm Design This project pursues a number of objectivesthat have been at the heart of importantnew developments in computational geometry.Chief among them is the issue ofalgorithm design for large datasets:how to deal with high dimensionality,uncertainty; how to optimize functionsapproximately in sublinear time; how to simplify andvisualize complex data;how to customize data structures to speed up search.The effort is to involve a mix of theoreticaland experimental investigations, with targetedapplications to surface simplification,3D shape matching, massive dataset visualization,and protein structure prediction.The theoretical issues involvecombinatorial geometry, algorithm designand basic complexity theory. This effort is aimed at deriving newcomputational methods for solvingproblems of a geometric or biological naturethat have resisted past investigationsbecause of one two reasons: either the inputdata is too massive to be processed directlyand it can only be "sampled" cleverly orthe number of variables is itself so highthat standard methods suffer from an exponential blowupin the time it takes to run them. Newdimension reduction techniques are neededto resolve this bottleneck.etric Algorithm Design This project pursues a number of objectivesthat have been at the heart of importantnew developments in computational geometry.Chief among them is the issue ofalgorithm design for large datasets:how to deal with high dimensionality,uncertainty; how to optimize functionsapproximately in sublinear time; how to simplify andvisualize complex data;how to customize data structures to speed up search.The effort is to involve a mix of theoreticaland experimental investigations, with targetedapplications to surface simplification,3D shape matching, massive dataset visualization,and protein structure prediction.The theoretical issues involvecombinatorial geometry, algorithm designand basic complexity theory. This effort is aimed at deriving newcomputational methods for solvingproblems of a geometric or biological naturethat have resisted past investigationsbecause of one two reasons: either the inputdata is too massive to be processed directlyand it can only be "sampled" cleverly orthe number of variables is itself so highthat standard methods suffer from an exponential blowupin the time it takes to run them. Newdimension reduction techniques are neededto resolve this bottleneck. The proposal is a careful outline of research work that may greatly aid in geometric data

0306283的特别摘要（Dobkin和Chazelle，普林斯顿大学，题目：几何算法设计的新方向）这个项目追求的目标是计算几何中重要的新发展的核心。其中主要的是大数据集的算法设计问题：如何处理高维，不确定性;如何在次线性时间内近似优化函数;如何简化和可视化复杂的数据;如何自定义数据结构以加速搜索。这项工作涉及理论和实验研究的混合，目标应用于表面简化，3D形状匹配，大规模数据集可视化和蛋白质结构预测。理论问题涉及组合几何，算法设计和基本复杂性理论。这一努力的目的是推导出新的计算方法来解决几何或生物性质的问题，这些问题由于以下两个原因而抵制了过去的调查：要么输入数据太大，无法直接处理，只能巧妙地“采样”，要么变量的数量本身太高，以至于标准方法在运行它们所需的时间内遭受指数爆炸。该项目的目标是实现计算几何领域的一系列重要发展，其中最重要的是大数据集的算法设计问题：如何处理高维、不确定性;如何在次线性时间内近似优化函数;如何简化和可视化复杂数据;如何在最短时间内实现最优解;如何在最短时间内实现最优解。如何自定义数据结构以加速搜索。这项工作涉及理论和实验研究的混合，目标应用于表面简化，3D形状匹配，大规模数据集可视化和蛋白质结构预测。理论问题涉及组合几何，算法设计和基本复杂性理论。这一努力的目的是推导出新的计算方法来解决几何或生物性质的问题，这些问题由于以下两个原因而抵制了过去的调查：要么输入数据太大，无法直接处理，只能巧妙地“采样”，要么变量的数量本身太高，以至于标准方法在运行它们所需的时间内遭受指数爆炸。需要新的降维技术来解决这个瓶颈。 该建议是一个仔细的研究工作纲要，可能会大大有助于几何数据