2D Fréchet Distance

Shape matching algorithms are an essential component to a wide range of cutting-edge technological sectors such as computer vision, computer aided design, robotics, medical imaging, and drug design. Any shape matching algorithm is based on a distance measure for the shapes under consideration. Due to the lack of other efficient algorithms, applications for surface matching in 3D usually use heuristic variants of the Hausdorff distance which are often not well-suited. The Fréchet distance is a distance measure that takes the continuity of the shapes into account, and is therefore generally a more appropriate distance measure than the Hausdorff distance. The Fréchet distance between polygonal curves can be computed in polynomial time, however computing the Fréchet distance for (two-dimensional) surfaces is already NP-hard. Except for the NP-hardness very little is known so far about the Fréchet distance of surfaces. It is known to be semi-computable, but it is unknown whether it is computable, and there are no approximation algorithms.

We address this problem by considering restricted classes of surfaces. For simple polygons, which may lie in two different planes, we have recently presented a polynomial time algorithm [Buchin et al. 2006] that is based on mapping an arbitrary triangulation of one polygon to the other polygon such that diagonals of the triangulation are mapped to shortest paths in the other polygon. We currently work on more general classes of two-dimensional surfaces. Possible candidates are triangulated polygons that have been folded along their diagonals.

Collaborators:

• Kevin Buchin, Free University Berlin, Germany.
• Maike Buchin, Free University Berlin, Germany.

Students:

• Evan Cordell
• Jessica Sherette
• Atlas F. Cook IV

Publications:

• "Fréchet Distance for Simple Polygons" (E. Cordell), Honors thesis, Tulane University, 2013.
• "Computing the Fréchet Distance between Folded Polygons" , (A.F. Cook IV, A. Driemel, J. Sherette, C. Wenk), Computational Geometry: Theory and Applications 50:1-16, 2015.
• "Fréchet Distance for Simple Polygons", (Evan Cordell), Honors Thesis, Department of Mathematics, Tulane University, 2013.
• "Partial Matching between Surfaces Using Fréchet Distance", (J. Sherette and C. Wenk), Scandinavian Symposium and Workshops on Algorithm Theory (SWAT): 13-23, Helsinki, Finland, 2012. [slides]
• "Computing the Fréchet Distance between Folded Polygons", (A.F. Cook IV, A. Driemel, S. Har-Peled, J. Sherette, C. Wenk), Algorithms and Data Structures Symposium (WADS): 267-278, Brooklyn, New York, 2011.
• "Partial Matching between Surfaces Using Fréchet Distance" (J. Sherette, C. Wenk), 21st Fall Workshop on Computational Geometry (2 pages), City College of New York, Manhattan, NY, 2011.
• "Computing the Fréchet Distance Between Polyhedral Surfaces with Acyclic Dual Graphs", (A.F. Cook IV, J. Sherette, C. Wenk), 19th Fall Workshop on Computational Geometry: 75-76, Tufts University, Medford, MA, 2009.
• ``Computing the Fréchet Distance Between Simple Polygons in Polynomial Time'' [pdf] (K. Buchin, M. Buchin, and C. Wenk), Proc. 22nd ACM Symp. on Computational Geometry (SoCG): 80-87, 2006, Sedona, Arizona.

Grants:

• "CAREER: Application and Theory of Geometric Shape Handling", NSF CCF-0643597, $400,468 , 3/1/2007 - 2/29/2012.