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 shapecomparison.
In the work on protein shapecomparison, 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


recognize protein domains, relatively large structures that occur in several different proteins. Some of the techniques are related to our
earlier work on shapecomparison 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 threedimensional problems. The major difficulty here is to avoid producing "slivers": tetrahedra
with nicely shaped faces but with nearzero
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
3space under polyhedral
convex distance functions.
Journal of Algorithms 29
(Nov 1998), 238255 (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), 197202
(with K. Kedem).
 Geometric pattern matching in $d$dimensional
space. Discrete and Computational Geometry 21, 2 (1999), 257274 (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), 104113 (with D. Huttenlocher, K. Kedem, and J. Kleinberg).

