On the complexity of measuring the similarity between geometric objects in higher dimensions
Michael Godau · Refubium (Universitätsbibliothek der Freien Universität Berlin) · 1999
In pattern recognition and quality control the comparison of geometric objects is an often considered problem. In order to quantify the similarity between geometric objects a natural approach is considering them as elements of some metric space and evaluating their degree of similarity by simply computing the distance between them. The geometric objects we consider in this thesis are curves, surfaces or analogues in higher dimensions usually seen as equivalence classes of parameterized curves, parameterized surfaces and so on. We assume the objects to be described by a finite structure. That means for curves that they consist of finitely many line segments and for surfaces that they consist of triangles and so on. A natural metric defining the similarity between them is the Fréchet distance, first described in 1906. Especially in the calculus of variations this is the standard metric considered. Algorithms for piecewise affine curves already have been investigated in different publications. The given algorithms for computing the distance between such curves have had a polynomial runtime of low degree. In higher dimensions it is not known whether there exists even a polynomial time algorithm. However, among other things, in this thesis it will be shown that the problem is NP-hard for higher dimensions. As a byproduct of this research we also prove some NP-hardness result in graph drawing. In search for a more efficient way to calculate the distance between those objects we investigate the well known Hausdorff metric as well. For this metric we give polynomial time algorithms for any dimension and we prove that for convex objects this metric coincides with the Fréchet metric.