Maike Buchin

On the computability of the Frechet distance between triangulated surfaces

Betreuer: Prof. Dr. Helmut Alt
Abschluss: PhD
Abgabedatum: 23.04.2007
Homepage des Autors:

Kurzbeschreibung

The Frechet distance is a metric for parameterized 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 Frechet distance between two surfaces is less than or equal a given threshold is NP-hard. It is not known, whether the Frechet distance between triangulated surfaces is computable. In this thesis, we study the computability of the Frechet distance between triangulated surfaces. We give three partial answers to the question whether it is computable. For triangulated surfaces, we show that the Frechet distance is semi-computable, a weaker notion of computability. For a variant of the Frechet distance, the weak Frechet distance, we show that it is polynomial time computable for triangulated surfaces. For a restricted class of surfaces, simple polygons, we show that the Frechet distance is polynomial time computable. Finally, we study a related question, the definition of a summed or average Frechet distance between curves. We show that none of several intuitive definitions fulfill the triangle inequality.

Downloads