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
