Ph.D. thesis : On the computability of the Frechet distance between triangulated surfaces
Advisor: Prof. Dr. Helmut Alt
The Fréchet distance is a metric for parametrized curves and surfaces. It is used in shape matching for measuring the similarity of geometric shapes. For polygonal curves, it can be computed in polynomial time. For triangulated surfaces, deciding whether the Fréchet distance between two surfaces is less than or equal a given threshold is NP-hard. It is not known, whether the Fréchet distance between triangulated surfaces is computable.
In this thesis, we study the computability of the Fréchet distance between triangulated surfaces. We give three partial answers to the question whether it is computable. For triangulated surfaces, we show that the Fréchet distance is semi-computable, a weaker notion of computability. For a variant of the Fréchet distance, the weak Fréchet distance, we show that it is polynomial time computable for triangulated surfaces. For a restricted class of surfaces, simple polygons, we show that the Fréchet distance is polynomial time computable.
Finally, we study a related question, the definition of a summed or average Fréchet distance between curves. We show that none of several intuitive definitions fulfill the triangle inequality.