| 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.