Carola Wenk's web pages.
|| 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.
- Atlas F. Cook IV
- Jeffrey Byrnes
- Jared Bennat
- ``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]
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''
(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
- "CAREER: Application and Theory of Geometric Shape
Handling", NSF CCF-0643597, $400,468 , 3/1/2007 - 2/29/2012.
Last modified by Carola Wenk,
cwenk -at- tulane -dot- edu ,