L. Paul Chew
Senior Research Associate

Applet

Research

My primary interest is the development and analysis of algorithms, particularly those that have practical applications. These practical applications have included placement, motion planning, shape comparison, computer vision, sensing, mesh generation, molecular matching, tools for analyzing/comparing protein shapes, and simulation of combustion. At Cornell, I have participated in research covering diverse application areas from computer vision to civil engineering to computational molecular biology.

• I invented/discovered backwards analysis, a now-widely-used technique for the design and analysis of randomized algorithms.

• Many of the numerical techniques for solving partial differential equations (PDEs) require the creation of a mesh, a subdivision of the region-of-interest into simple shapes such as triangles or tetrahedra. I created one of the first mesh-generation algorithm to offer a mathematical guarantee about the quality of the resulting mesh.

• I’ve worked on various aspects of parallel computation, primarily for the purpose of parallel mesh-generation. I’m currently working with Keshav Pingali, Kavita Bala, Milind Kulkarni, Bruce Walter, and Ganesh Ramanarayanan on the use of optimistic parallelization to speed up complex “irregular” applications (i.e., applications that manipulate large, pointer-based data structures such as graphs).

• In work with Klara Kedem, Jon Kleinberg, and Dan Huttenlocher, I developed the URMS (Unit-vector Root Mean Square) distance for comparing protein structures. The URMS distance is a variant of the RMS distance: instead of comparing points, we compare unit vectors. The compared vectors are those between adjacent α-carbons along the protein backbone. The URMS distance has been used as part of the evaluation process for CAFASP (Critical Assessment of Fully Automated Structure Prediction), a “contest” held every two years to evaluate the capabilities of web-based, automated systems for protein structure prediction.

• With Klara Kedem, I developed the consensus structure for a protein family, a protein-like structure that provides a compact summary of the significant structural information for a protein family. If all members of the protein family exhibit a geometric relationship between corresponding α-carbons then that relationship is preserved in the consensus structure. In particular, distances and angles that are consistent across family members are preserved.

• I introduced the concept now referred to as geometric spanners (I did not use this term in my original paper). In the plane, a geometric spanner is a graph such that, for each pair of vertices, the shortest path in the graph is within a constant factor of the straight-line Euclidean distance between the vertices. Spanners have been useful for proximity problems, motion planning, and telecommunication networks.

Selected Papers

• Isana Veksler-Lublinsky, Danny Barash, Chai Avisar, Einav Troim, Paul Chew, and Klara Kedem, FASH: A web application for nucleotides sequence search, Source Code for Biology and Medicine 2008, 3:9 (27 May 2008).

• Milind Kulkarni, Keshav Pingali, Ganesh Ramanarayanan, Bruce Walter, Kavita Bala and L. Paul Chew, Optimistic Parallelism Benefits From Data Partitioning, Architectural Support for Programming Languages and Operating Systems (ASPLOS), March 2008, 233-243.

• Milind Kulkarni, Keshav Pingali, Bruce Walter, Ganesh Ramanarayanan, Kavita Bala, and Paul Chew, Optimistic Parallelism Requires Abstractions, Proceedings of the ACM SIGPLAN 2007 Conference on Programming Language Design and Implementation (PLDI), 2007, 211-222.

• B. Panda, M. Riedewald, S. B. Pope, J. Gehrke, L. P. Chew, Indexing for Function Approximation, in Proceedings of Int. Conf. on Very Large Databases (VLDB), September 2006, 523-534.

• Milind Kulkarni, L. Paul Chew, and Keshav Pingali, Using Transactions in Delaunay Mesh Generation, Workshop on Transactional Memory Workloads (WTW), June 2006.

• L. Paul Chew, Exact Computation of Protein Structure Similarity, Proceedings of the 22nd ACM Symposium on Computational Geometry (2006), ACM Press, 468-474.

• Paul Chew, Jason Shepherd, John P. Steinbrenner, Alper Üngör (Guest Editors), Twelfth International Meshing Roundtable special issue, Engineering with Computers, 21:1 (2005).

• Paul Chew and Alper Üngör (Guest Editors), Special Issue: Selected Papers from the 12th International Meshing Roundtable (IMR), International Journal of Computational Geometry and Applications, 15:1 (2005).

• Démian Nave, Nikos Chrisochoides, and L. Paul Chew, Guaranteed-quality parallel Delaunay refinement for restricted polyhedral domains, Computational Geometry (COMGEO), 28:2-3, 191-215 (2004).

• Amit Weisman, L. Paul Chew, and Klara Kedem, Voronoi diagrams of moving points in the plane and of lines in space: tight bounds for simple configurations, Information Processing Letters (IPL), 92:5, 245-251, (2004).

• L. P. Chew and K. Kedem, Finding the Consensus Shape for a Protein Family, Algorithmica, Volume 38 Number 1, October 2003, 115-129.

• L. Paul Chew, Nikos Chrisochoides, S. Gopalsamy, Gerd Heber, Anthony R. Ingraffea, Edward Luke, Joaquim B. Cavalcante Neto, Keshav Pingali, Alan M. Shih, Bharat K. Soni, Paul Stodghill, David Thompson, Stephen A. Vavasis, Paul A. Wawrzynek, Computational Science Simulations Based on Web Services, International Conference on Computational Science 2003, 299-308.

• L. Paul Chew, Stephen A. Vavasis, S. Gopalsamy, TzuYi Yu, Bharat K. Soni: A Concise Representation of Geometry Suitable for Mesh Generation, Proceedings of the 11th International Meshing Roundtable (IMR) 2002, 275-283.

• L. Paul Chew, Haggai David, Matthew J. Katz, Klara Kedem, Walking around fat obstacles, Information Processing Letters (IPL), 83:3, 135-140, (2002).

• L. Paul Chew, Klara Kedem, Finding the consensus shape for a protein family, Proceedings of the 18th Annual Symposium on Computational Geometry (SoCG) 2002, 64-73.

• Démian Nave, Nikos Chrisochoides, L. Paul Chew, Guaranteed-quality parallel Delaunay refinement for restricted polyhedral domains, Proceedings of the 18th Annual Symposium on Computational Geometry (SoCG) 2002, 135-144.

• Bruce Carter, Chuin-Shan Chen, L. Paul Chew, Nikos Chrisochoides, Guang R. Gao, Gerd Heber, Anthony R. Ingraffea, Roland Krause, Chris Myers, Démian Nave, Keshav Pingali, Paul Stodghill, Stephen A. Vavasis, Paul A. Wawrzynek, Parallel FEM Simulation of Crack Propagation - Challenges, Status, and Perspectives, IPDPS Workshops 2000, 443-449.

• Marshall W. Bern, David Eppstein, Pankaj K. Agarwal, Nina Amenta, L. Paul Chew, Tamal K. Dey, David P. Dobkin, Herbert Edelsbrunner, Cindy Grimm, Leonidas J. Guibas, John Harer, Joel Hass, Andrew Hicks, Carroll K. Johnson, Gilad Lerman, David Letscher, Paul E. Plassmann, Eric Sedgwick, Jack Snoeyink, Jeff Weeks, Chee-Keng Yap, Denis Zorin, Emerging Challenges in Computational Topology, CoRR cs.CG/9909001 (1999).

• L. Paul Chew, Dorit Dor, Alon Efrat, Klara Kedem, Geometric Pattern Matching in d-Dimensional Space, Discrete & Computational Geometry (DCG) 21:2, 257-274 (1999).

• K. Kedem, L. P. Chew, and R. Elber, Unit-vector RMS (URMS) as a tool to analyze molecular dynamics trajectories, Proteins: Structure, Function and Genetics, 37 (1999), 554-564.

• L. P. Chew, D. Huttenlocher, K. Kedem, and J. Kleinberg, Fast Detection of Common Geometric Substructure in Proteins, Journal of Computational Biology (JCB), 6:3 (1999), 313-325.

• L. P. Chew and K. Kedem, Getting around a lower bound for the minimum Hausdorff distance, Computational Geometry (COMGEO), 10 (1998), 197-202.

• L. P. Chew, K. Kedem, M. Sharir, B. Taganski and E. Welzl, Voronoi diagrams of lines in 3-space under polyhedral convex distance functions, Journal of Algorithms, 29 (1998), 238-255.

• L. Paul Chew, Nikos Chrisochoides, and Florian Sukup, Parallel Constrained Delaunay Meshing, Trends in Unstructured Mesh Generation, AMD-Vol. 220 (1997), ASME, 89-96.

• L. P. Chew and S. J. Fortune, Sorting Helps for Voronoi Diagrams, Algorithmica, 18 (1997), 217-228.

• L. P. Chew, Near-Quadratic Bounds for the L₁ Voronoi Diagram of Moving Points, Computational Geometry (COMGEO), 7 (1997), 73-80.

• L. Paul Chew, Michael T. Goodrich, Daniel P. Huttenlocher, Klara Kedem, Jon M. Kleinberg, Dina Kravets, Geometric Pattern Matching Under Euclidean Motion, Computational Geometry (COMGEO), 7, 113-124 (1997).

• L. Paul Chew, Guaranteed-Quality Delaunay Meshing in 3D (Short Version), Proceedings of the Thirteenth Annual Symposium on Computational Geometry (SoCG), 1997, 391-393.

• Srinivasa Rao Arikati, Danny Z. Chen, L. Paul Chew, Gautam Das, Michiel H. M. Smid, Christos D. Zaroliagis, Planar Spanners and Approximate Shortest Path Queries among Obstacles in the Plane, European Symposium on Algorithms (ESA), 1996, 514-528.

• L. Paul Chew, Dorit Dor, Alon Efrat, Klara Kedem, Geometric Pattern Matching in d-Dimensional Space, European Symposium on Algorithms (ESA), 1995, 264-279.

• Marshall W. Bern, L. Paul Chew, David Eppstein, Jim Ruppert, Dihedral Bounds for Mesh Generation in High Dimensions, Proceedings of the Sixth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 1995, 189-196.

• L. Paul Chew, Klara Kedem, Micha Sharir, Boaz Tagansky, Emo Welzl, Voronoi Diagrams of Lines in 3-Space Under Polyhedral Convex Distance Functions, Proceedings of the Sixth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 1995, 197-204.

• R. G. Brown, L. P. Chew, and B. R. Donald, Localization and Map-making Algorithms for Mobile Robots, Proceedings of the IASTED International Conference on Robotics and Manufacturing (1993), 185-190.

• L. Paul Chew, Michael T. Goodrich, Daniel P. Huttenlocher, Klara Kedem, Jon M. Kleinberg, Dina Kravets, Geometric Pattern Matching Under Euclidean Motion, Proceedings of the 5th Canadian Conference on Computational Geometry (CCCG), 1993, 151-156.

• L. Paul Chew, Near-quadratic Bounds for the L₁ Voronoi Diagram of Moving Points, Proceedings of the 5th Canadian Conference on Computational Geometry (CCCG), 1993, 364-369.

• L. Paul Chew, Klara Kedem, A Convex Polygon Among Polygonal Obstacles: Placement and High-clearance Motion, Computational Geometry (COMGEO) 3, 59-89 (1993).

• L. Paul Chew, Guaranteed-Quality Mesh Generation for Curved Surfaces, Proceedings of the Ninth Symposium on Computational Geometry (1993), ACM Press, 274-280.

• L. Paul Chew, Klara Kedem, Improvements on Geometric Pattern Matching Problems, Scandinavian Workshop on Algorithm Theory (SWAT), 1992, 318-325.

• L. P. Chew, E. M. Arkin, D. P. Huttenlocher, K. Kedem, and J. S. B. Mitchell, An Efficiently Computable Metric for Comparing Polygonal Shapes, IEEE Transactions on Pattern Analysis and Machine Intelligence, 13:3 (1991), 209-216.

• Paul Chew and Keith Marzullo, Masking Failures of Multidimensional Sensors, Tenth Symposium on Reliable Distributed Systems (SRDS) 1991: 32-41.

• Esther M. Arkin, L. Paul Chew, Daniel P. Huttenlocher, Klara Kedem, Joseph S. B. Mitchell, An Efficiently Computable Metric for Comparing Polygonal Shapes, Proceedings of the First Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 1990, 129-137.

• L. Paul Chew, Constrained Delaunay Triangulations, Algorithmica 4:1, 97-108 (1989).

• L. Paul Chew, Klara Kedem, Placing the Largest Similar Copy of a Convex Polygon Among Polygonal Obstacles, Proceedings of the Fifth Annual Symposium on Computational Geometry (SoCG), 1989, 167-173.

• L. Paul Chew, Guaranteed-Quality Triangular Meshes, Department of Computer Science Tech Report 89-983, Cornell University (1989). [Although this paper has never appeared in a journal, it has had great influence. This was the first Delaunay-triangulation-based mesh-generation algorithm to provide a mathematical guarantee on the quality of the resulting mesh.]

• L. P. Chew, There are Planar Graphs Almost as Good as the Complete Graph, Journal of Computer and System Sciences, 39:2 (1989), 205-219.

• L. Paul Chew, Constrained Delaunay Triangulations, Proceedings of the Third Annual Symposium on Computational Geometry (SoCG), 1987, 215-222.

• L. P. Chew, Building Voronoi Diagrams for Convex Polygons in Linear Expected Time, Technical Report PCS-TR90-147, Dept of Math and Computer Science, Dartmouth College, 1986. [Although this paper has never appeared in a journal, it has had great influence. This paper introduced the idea of backwards analysis, a now widely-used technique for the design and analysis of randomized algorithms.]

• Paul Chew, There is a Planar Graph Almost as Good as the Complete Graph, Symposium on Computational Geometry (1986), 169-177.

• L. P. Chew, Planning the Shortest Path for a Disc in O(n² log n) Time, Proceedings of the First Annual Symposium on Computational Geometry (1985), 214–220.

• L. P. Chew and R. L. Drysdale, Voronoi Diagrams Based on Convex Distance Functions, Proceedings of the First Annual Symposium on Computational Geometry (1985), 235-244.

• Paul Chew, Unique Normal Forms in Term Rewriting Systems with Repeated Variables, Proceedings of the 13th Annual ACM Symposium on Theory of Computing (STOC),1981, 7-18.

• Paul Chew and Michael Machtey, A Note on Structure and Looking Back Applied to the Complexity of Computable Functions, J. Comput. Syst. Sci. (JCSS) 22:1, 53-59 (1981).

• Paul Chew, An Improved Algorithm for Computing With Equations, 21st Annual Symposium on Foundations of Computer Science (FOCS) 1980, 108-117.

Recent Teaching

• 2008
  CS 3810: Introduction to Theory of Computing [summer]
  CS 212: Java Practicum [spring]
  CS 100M: Introduction to Computer Programming (Matlab) [spring]

• 2007
  CS 212: Java Practicum [fall]
  CS 482: Introduction to Analysis of Algorithms [summer]
  CS 482: Introduction to Analysis of Algorithms [spring]
  CS 100M: Introduction to Computer Programming (Matlab) [spring]

• 2006
  CS 211: Computers and Programming [fall]
  CS 100M: Introduction to Computer Programming (Matlab) [spring]

• 2005
  CS 211: Computers and Programming [fall]
  CS 482: Introduction to Analysis of Algorithms [spring]

• 2004
  CS 212: Java Practicum [spring]

• 2003
  CS 426: Introduction to Computational Biology [fall]

Job History