Computing the Frechet Distance between Real-Valued Surfaces

The Frechet distance is a well-studied measure for the similarity of shapes. While efficient algorithms for computing the Frechet distance between curves exist, there are only few results on the Frechet distance between surfaces. Recent work has shown that the Frechet distance is computable between piecewise linear functions f and g: M -> R-k with M a triangulated surface of genus zero. We focus on the case k = 1 and M being a topological sphere or disk with constant boundary. Intuitively, we measure the distance between terrains based solely on the height function. Our main result is that in this case computing the Frechet distance between f and g is in NP. We additionally show that already for k = 1, computing a factor 2 - epsilon approximation of the Frechet distance is NP-hard, showing that this problem is in fact NP-complete. We also define an intermediate distance, between contour trees, which we also show to be NP-complete to compute. Finally, we discuss how our and other distance measures between contour trees relate to each other.