Shape Matching of Curves

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. Due to increasing amounts of data in various applications it has become more and more important to automate Shape Matching tasks with algorithms that give performance and quality guarantees in order to build a sound theoretical foundation that is applicable in a wide range of contexts. This project focuses on geometric shapes described by polygonal curves and adequate distance measures such as the Fréchet distance.

The Fréchet distance is a distance measure for continuous shapes such as curves and surfaces. Since it takes the continuity of the shapes into account it is usually a more appropriate distance measure than the often used Hausdorff distance, which fails to take into account this important factor. However, up to now the Fréchet distance is generally not very well-understood. Currently, lgorithms for curves that compute the Fréchet distance or minimize it under transformations take too much time to be useful in practice. This requires research into approximation algorithms, consideration of simpler shape classes motivated by applications, development of output-sensitive algorithms, and undertaking of theoretical complexity analyses such as providing lower bounds, in order to increase the knowledge-base towards the practical utilization of the Fréchet distance.

Students:

• Atlas F. Cook IV
• Jeffrey Byrnes
• Jared Bennat

Publications:

• ``Geodesic Fréchet Distance Inside a Simple Polygon'' [pdf] (A.F. Cook IV and C. Wenk), Proceedings of the 25th International Symposium on Theoretical Aspects of Computer Science (STACS): 193-204, 2008, Bordeaux, France.
• "Min-Link Shortest Path Maps and Fréchet Distance", [pdf] (A.F. Cook IV, C. Wenk) UTSA Technical Report CS-TR-2008-0011, 2008.
• "Geodesic Fréchet Distance With Polygonal Obstacles", [pdf] (A.F. Cook IV, C. Wenk) UTSA Technical Report CS-TR-2008-0010, 2008.
• "Geodesic Fréchet Distance Inside a Simple Polygon" [pdf] (A.F.Cook, C. Wenk), 17th Fall Workshop on Computational Geometry, 2007, IBM Hawthorne.
• ``Fréchet Distance for Curves, Revisited'' [pdf] (B. Aronov, S. Har-Peled, C. Knauer, Y. Wang, and C. Wenk), Proceedings of the 14th Annual European Symposium on Algorithms (ESA): 52-63, LNCS 4168, 2006, Zurich, Switzerland.
• ``Comparison of Distance Measures for Planar Curves'' [ps.gz, pdf] (H. Alt, C. Knauer, and C. Wenk), Algorithmica (special issue on shape algorithmics) 38(2):45-58, 2004.
• ``Bounding the Fréchet distance by the Hausdorff distance'' [ps.gz, pdf] (H. Alt, C. Knauer, and C. Wenk), Proc. 17th European Workshop on Computational Geometry: 166-169, 2001, Berlin, Germany
• ``Matching polygonal curves with respect to the Fréchet distance'' (H. Alt, C. Knauer, C. Wenk), Proc. 18th Int. Symp. Theoretical Aspects of Computer Science (STACS): 63-74, 2001, Dresden, Germany

Grants:

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