Algorithms And Hardness Results for Measuring Similarity Using Fréchet Distance




Sherette, Jonathan Lee

Journal Title

Journal ISSN

Volume Title



This thesis explores the problem of computing the similarity of surfaces with a focus on the Fréchet distance as well as different variants of it. The ability to efficiently and accurately compare surfaces is important for many real world applications which range from problems in computer aided design to ones in evolutionary biology. The methods often used in practice to compare surfaces are heuristics and thus make no guarantees about the compared surfaces. The Fréchet distance offers a natural metric of similarity for comparing continuous shapes such as surfaces. Unfortunately, the Fréchet distance is known to be difficult to compute for many natural classes of surfaces so, in addition to developing new algorithms to compute the Fréchet distance between surfaces, we also explore core problems in computing Fréchet distance. In particular, we consider computing the Fréchet distance for a class of surfaces which we call folded polygons. We also introduce a partial variant of Fréchet distance for surfaces. From these results we develop and explore the simple curve embedding problem, the Flippy distance, and the double Fréchet distance which are generalizations of core problems observed in computing the Fréchet distance between surfaces. Research in these core problems may allow for development of similarity metrics which are both accurate but also easier to compute for real world problems.


This item is available only to currently enrolled UTSA students, faculty or staff. To download, navigate to Log In in the top right-hand corner of this screen, then select Log in with my UTSA ID.


algorithms, Fréchet distance, similarity metrics, surface matching



Computer Science