Geodesic Distances for Shapes

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 applications where the shapes lie on a surface the distance between two points should be measured along the surface as the length of a geodesic, i.e., a shortest path along the surface, between the points. This is a completely new area and has great utilization potential in military and GIS applications in which objects traveling on various terrains are involved.

This project initiates a general study of such geodesic distance measures. It is essential to study available shortest paths algorithms and to integrate them into known algorithms for Shape Matching tasks that involve a variety of distances, among them the Fréchet distance and the Hausdorff distance.

Former Students:

• Atlas Cook (PhD student)

Publications:

• ``Geodesic Fréchet Distance Inside a Simple Polygon'' [pdf] (A.F. Cook IV and C. Wenk), accepted to ACM Transactions on Algorithms.
• ``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.

Grants:

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