Senior Research Associate
chew@cs.cornell.edu
http://www.cs.cornell.edu/chew/chew.html
Ph.D. Purdue University, 1981
My primary interest is in geometric algorithms with an emphasis on practical applications. These practical applications have included placement, motion planning, shape comparison, vision, sensing, mesh generation, molecular matching, and protein shape-comparison.
In the work on protein shape-comparison, Klara Kedem, Jon Kleinberg, Dan Huttenlocher, and I have developed efficient algorithms for determining whether two proteins have any portions that are of similar shape. We have also developed techniques for grouping small matching portions to recognize protein domains, relatively large structures that occur in several different proteins. Some of the techniques are related to our earlier work on shape-comparison for computer vision. In work with Ron Elber and K. Kedem, we have shown how these shape comparison methods can be used to help analyze molecular dynamics trajectories (computer simulations of protein motion).
My work on mesh generation has been motivated by the finite element method for finding approximate solutions to partial differential equations. The first step of this method is to create a mesh, i.e. to divide the given problem region into simple shapes called elements (usually triangles or quadrilaterals in 2D, tetrahedra or hexahedra in 3D). A number of algorithms have been developed to automate this process, but most of them don’t guarantee the quality of the resulting mesh (e.g. a triangle may cross a region boundary or there may be some flat triangles, leading to poor error bounds). I developed efficient techniques for producing meshes of guaranteed quality for problems in the plane and for curved surfaces. The triangles produced are close to equilateral in shape; all region boundaries are respected; and the user can control the element density, producing small elements in “interesting” regions and large elements elsewhere.
I extended this work to produce tetrahedral meshes for three-dimensional problems. The major difficulty here is to avoid producing “slivers”: tetrahedra with nicely shaped faces but with near-zero volume. I showed that slivers can be avoided by choosing each new mesh point randomly within a small specified volume. The randomness helps; a good mesh point – one that does not form any slivers – can be found in constant expected time.
This work is being used in a large, multi-disciplinary project for fracture simulation on parallel computers. Other researchers working on this project are Keshav Pingali, Steve Vavasis, Paul Stodghill, Tony Ingraffea (Civil Engineering), Gao Guong-Rong (CS, Delaware), and Nikos Chrisochoides (CS, College of William & Mary). This group is developing guaranteed-quality parallel mesh generators, new preconditioners for sparse linear systems solvers, compilation techniques for sparse matrix codes, and multi-threaded runtime systems.
Professional Activities
Associate Editor: Pattern Recognition, The Journal of the Pattern Recognition Society.
Referee: 16th Annual Symposium on Computational Geometry.
Publications
“Fast Detection of Common Geometric Substructure in Proteins.” Journal of Computational Biology, 6:3 (1999), 313–325 (with D. Huttenlocher, K. Kedem, and J. Kleinberg).
“Unit-vector RMS (URMS) as a tool to analyze molecular dynamics trajectories.” Proteins: Structure, Function and Genetics, 37 (1999), 554–564 (with K. Kedem and R. Elber).
“Parallel FEM Simulation of Crack Propagation—Challenges, Status, and Perspectives.” Proceedings of Irregular 2000, (2000), (with B. Carter, C.S. Chen, G. Heber, A.R. Ingraffea, R. Krause, C. Myers, P.A. Wawrzynek, K. Pingali, P. Stodghill, S. Vavasis, N. Chrisochoides, D. Nave, and G.R. Gao).
