  A suitable measure for the similarity of shapes represented by parameterized
curves or surfaces is the Fr\'echet distance. Whereas efficient algorithms are
known for computing the Fr\'echet distance of polygonal curves, the same
problem for triangulated surfaces is NP-hard. Furthermore, it remained open
whether it is computable at all. Here, using a discrete approximation we show
that it is {\em upper semi-computable}, i.e., there is a non-halting Turing
machine which produces a monotone decreasing sequence of rationals converging
to the result. It follows that the decision problem, whether the Fr\'echet
distance of two given surfaces lies below some specified value, is recursively
enumerable.
  Furthermore, we show that a relaxed version of the problem, the computation
of the {\em weak Fr\'echet distance} can be solved in polynomial time. For
this, we give a computable characterization of the weak Fr\'echet distance in a
geometric data structure called the {\em free space diagram}.
