New Directions in Geometric Algorithm Design

0306283的特别摘要(Dobkin和Chazelle，普林斯顿大学，标题：几何算法设计的新方向)这个项目追求一些目标，这些目标一直是计算几何新发展的核心。其中最主要的是大数据集的算法设计问题：如何处理高维、不确定性；如何在近似线性时间内优化函数；如何简化复杂数据并使其可视化；如何定制数据结构以加快搜索速度。努力涉及理论和实验研究的结合，有针对性地应用于表面简化、3D形状匹配、海量数据集可视化和蛋白质结构预测。理论问题涉及组合几何、算法设计和基本复杂性理论。这一努力旨在为解决几何或生物性质的问题找到新的计算方法，这些问题因以下两个原因之一而受到抵制：一是输入数据太大，无法直接处理，只能巧妙地对其进行“采样”；二是变量数量太多，以至于标准方法在运行它们所需的时间内遭受了指数级的爆炸。需要新的降维技术来解决这一瓶颈。计量算法设计这个项目追求一些目标，这些目标一直是计算几何新发展的核心。其中最主要的是大数据集的算法设计问题：如何处理高维、不确定性；如何在次线性时间内近似优化函数；如何简化和可视化复杂数据；如何定制数据结构以加快搜索速度。努力涉及理论和实验研究的结合，有针对性地应用于表面简化、3D形状匹配、海量数据集可视化和蛋白质结构预测。理论问题包括组合几何、算法设计和基本复杂性理论。这一努力旨在为解决几何或生物性质的问题找到新的计算方法，这些问题因以下两个原因之一而受到抵制：一是输入数据太大，无法直接处理，只能巧妙地对其进行“采样”；二是变量数量太多，以至于标准方法在运行它们所需的时间内遭受了指数级的爆炸。需要新的降维技术来解决这一瓶颈。该提案是对研究工作的仔细概述，可能会对几何数据有很大帮助

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