On the complexity of measuring the similarity between geometric objects in higher dimensions

Abstract

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.

In der Mustererkennung und der Qualitätskontrolle ist der Vergleich geometrischer Objekte ein oft betrachtetes Problem. Um die Ähnlichkeit zwischen Objekten in Zahlen zu fassen, ist es ein natürlicher Ansatz, diese als Elemente eines metrischen Raumes aufzufassen und den Grad ihrer Ähnlichkeit als den Abstand zwischen ihnen.

Die geometrischen Objekte, die hier betrachtet werden, sind Kurven, Flächen oder Analoga in höheren Dimensionen, welche für gewöhnlich als Äquivalenzklassen parametrisierter Kurven, parametrisierter Flächen und so weiter betrachtet werden. Wir nehmen an, daß diese Objekte durch eine endliche Struktur beschrieben werden. Das bedeutet für Kurven, daß sie aus endlich vielen Strecken bestehen, für Flächen, daß sie aus endlich vielen Dreiecken bestehen usw.

Eine natürliche Metrik, welche die Ähnlichkeit zwischen ihnen ausdrückt, ist die Fréchetmetrik, zuerst erwähnt 1906. Speziell in der Variationsrechnung ist dies die dort betrachtete Standardmetrik.

Algorithmen für stückweise affine Kurven wurden bereits in anderen Arbeiten untersucht. Die darin für die Abstandsmessung solcher Kurven gegebenen Algorithmen hatten polynomiale Laufzeiten geringer Laufzeit.

In höheren Dimensionen ist nicht einmal bekannt, ob ein Polynomialzeitalgorithmus existiert. Unter anderem wird in dieser Arbeit gezeigt, daß das Problem NP-schwer ist für höhere Dimensionen. Als Nebenergebnis dieser Forschung wird ein weiteres NP-Schwerheitsergebnis aus dem Gebiet des Graphenzeichnens bewiesen.

Auf der Suche nach einem effizienteren Weg, den Abstand zwischen solchen Objekten zu berechnen, wird ferner die wohlbekannte Hausdorffmetrik untersucht. Für diese Metrik werden Polynomialzeitalgorithmen für jede Dimension angegeben und bewiesen, daß diese Metrik für konvexe Objekte mit der Fréchetmetrik übereinstimmt.