1998 - 1999 CS Annual Report                                                        Researchers
choices.gif (4488 bytes)
 

L. Paul Chew

Senior Research Associate
chew@cs.cornell.edu

PhD Purdue, 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, K. Kedem, J. Kleinberg, D. 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 

 chew.tif (90588 bytes)
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 R. 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. 

Professional Activities 
  • Referee: 40th Annual Symposium on the Foundations International Journal for Numerical Methods in Engineering 
Lectures 
  • Recent work on 3D meshing. DARPA RaDEO PI Meeting, Seattle, WA, Nov 1998. 
  • Fast detection of common geometric substructure in proteins. Third Annual International Conference on Computational Molecular Biology (RECOMB 99), Lyon, France, Apr. 1999.
Publications 
  • Voronoi diagrams of lines in 3-space under polyhedral convex distance functions.
    Journal of Algorithms 29 (Nov 1998), 238-255 (with K. Kedem, M. Sharir,  Taganski and E. Welzl). 
  • Getting around a lower bound for the minimum Hausdorff distance. Computational Geometry: Theory and Applications 10 (1998), 197-202 (with K. Kedem). 
  • Geometric pattern matching in $d$-dimensional space. Discrete and Computational Geometry 21, 2 (1999), 257-274 (with D. Dor, A. Efrat, and K. Kedem). 
  • Fast detection of common geometric substructure in proteins. RECOMB 99: Proceedings of the Third Annual International Conference on Computational Molecular Biology, ACM Press, (Apr. 1999), 104-113 (with D. Huttenlocher, K. Kedem, and J. Kleinberg).