New Directions in 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