Annamaria B. Amenta - US grants

This project concerns the problem of reconstructing a two- dimensional surface, such as the outside of a real object, from a collection of sample points. The problem is important for building models in computer graphics, and in other areas of science and engineering. A new algorithm has been developed which is provably correct and efficient, based on the Delaunay triangulation of the samples. An innovative aspect of the algorithm is that the samples do not have to be evenly distributed over the object - detailed areas can be sampled densely and smooth areas can be sampled sparsely. The basic algorithm will be tested in various applications, each requiring different extensions or modifications, and the application of the theory to other problems in geometric modeling will be studied.

New technology for capturing shape data from the real world
requires new algorithms to interpret and use it. Building on
new ideas about reconstructing a surface from a set of
points in three-dimensional space, we consider algorithms
for computing different shape representations, and for
aligning point sets to each other. We look for simple,
effective yet provably correct algorithms, using tools from
computational geometry but drawing on the huge body of
previous work in computer vision and graphics. This work
complements our teaching in graphics and algorithms, and
helps us train graduate students in research.

0121682 and 0121651
Amenta, Hillis, and St. John
Defining and understanding the evolutionary relationships among species is fundamental to contemporary biology and the application of the comparative method in the life sciences. The results of such evolutionary research can be represented by a branching sequence of relatedness among species known as a phylogeny. Because of the geometric resemblance of a phylogeny to the branches of a tree, a phylogeny can be thought of as a tree of life. The proposed collaborative research by biologists and computer scientists at University of Texas-Austin and at CUNY-Lehman College in New York will provide specialized visualization and data mining tools to facilitate creation of a "Tree of Life" for all living organisms on the earth. This includes the development and refinement of algorithms to visualize and analyze multiple complex data sets for large numbers of species. More specifically, this project will: (1) integrate biological data through visualization and clustering techniques developed by computer scientists, and (2) apply these tools to taxa which comprise very large numbers of species with topologically complex and varied tree structures. The interdisciplinary team of biologists and computer scientists will integrate their newly developed software with existing computational tools in systematic biology, and make them freely available to and easily used by the scientific community. The project involves substantive efforts to provide undergraduates and students from under-represented groups with the opportunity to collaborate with scientists throughout the academic year and summer.