L. Paul ChewSenior Research Associate PhD Purdue, 1981My 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. Sometimes proteins will have several matching portions; we can group these |
 |
| portions, allowing us to recognize protein domains, which are relatively large structures that occur in several different proteins. This work on proteins is related to our earlier work on shape-comparison for computer vision. | |
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. My new technique is based on the idea of choosing each new mesh point randomly within a small specified volume. I showed how to choose a new mesh point, in constant expected time, that is guaranteed not to form new slivers.
Professional Activities
Reviewer: Mathematical Programming, John Wiley and Sons.
Lectures
Active models in support of collaborative engineering. DARPA Structures Group PI Meeting, Philadelphia, Oct. 1998.
Provable quality 3d meshing. DARPA RaDEO PI Meeting, Nashville, TN, May 1998. Parallel constrained Delaunay meshing. Trends in Unstructured Mesh Generation, AMD 220 (1997), ASME, 89-96 (with N. Chrisochoides and F. Sukup).