New Directions in Geometric Algorithm Design

Princeton University, Princeton NJ

Investigators

Abstract

Special Abstract for 0306283 (Dobkin and Chazelle, Princeton U, Title: New Directions in Geometric Algorithm Design This project pursues a number of objectives that have been at the heart of important new developments in computational geometry. Chief among them is the issue of algorithm design for large datasets: how to deal with high dimensionality, uncertainty; how to optimize functions approximately in sublinear time; how to simplify and visualize complex data; how to customize data structures to speed up search. The effort is to involve a mix of theoretical and experimental investigations, with targeted applications to surface simplification, 3D shape matching, massive dataset visualization, and protein structure prediction. The theoretical issues involve combinatorial geometry, algorithm design and basic complexity theory. This effort is aimed at deriving new computational methods for solving problems of a geometric or biological nature that have resisted past investigations because of one two reasons: either the input data is too massive to be processed directly and it can only be "sampled" cleverly or the number of variables is itself so high that standard methods suffer from an exponential blowup in the time it takes to run them. New dimension reduction techniques are needed to resolve this bottleneck. etric Algorithm Design This project pursues a number of objectives that have been at the heart of important new developments in computational geometry. Chief among them is the issue of algorithm design for large datasets: how to deal with high dimensionality, uncertainty; how to optimize functions approximately in sublinear time; how to simplify and visualize complex data; how to customize data structures to speed up search. The effort is to involve a mix of theoretical and experimental investigations, with targeted applications to surface simplification, 3D shape matching, massive dataset visualization, and protein structure prediction. The theoretical issues involve combinatorial geometry, algorithm design and basic complexity theory. This effort is aimed at deriving new computational methods for solving problems of a geometric or biological nature that have resisted past investigations because of one two reasons: either the input data is too massive to be processed directly and it can only be "sampled" cleverly or the number of variables is itself so high that standard methods suffer from an exponential blowup in the time it takes to run them. New dimension reduction techniques are needed to resolve this bottleneck. The proposal is a careful outline of research work that may greatly aid in geometric data