Semi-Computability of the Frechet Distance Between Surfaces
Helmut Alt, Maike Buchin · 2005
The Frechet distance is a distance measure for pa- rameterized curves or surfaces. Using a discrete ap- proximation, we show that for triangulated surfaces it is upper semi-computable, i.e., there is a non-halting Turing machine which produces a monotone decreas- ing sequence of rationals converging to the result. It follows that the decision problem, whether the Frechet distance of two given surfaces lies below some speci- fied value, is recursively enumerable.