On the Decidability of the Fréchet Distance between Surfaces
Amir Nayyeri, Hanzhong Xu · Society for Industrial and Applied Mathematics eBooks · 2018
We show that the Fréchet distance between two piecewise linear surfaces can be decided in finite time, hence, the problem is decidable. For the special case that one of the surfaces is a triangle, we show that the problem is in PSPACE. In both cases, our computational model is a Turing Machine, and our algorithms rely on Canny's result [STOC 1988] that the existential theory of the real numbers is decidable in PSPACE.