Congruence Testing for Point Sets in 4-Space

Abstract

Congruence is the geometric concept of being the same up to rotations and translations in Euclidean space. As congruence is a fundamental concept in geometry, it has drawn broad attentions from the computational geometry community for a long time whether the curse of dimensionality applies to congruence testing. We developed a deterministic optimal-runningtime algorithm for congruence testing in 4-space. To understand the importance of the main algorithm in the historical context, we provide a survey about the computational model and the previous work on congruence testing algorithms. The crucial ingredients of the algorithm are explained component by component. These include general 4-dimensional rotations, angles between linear subspaces, and the Plücker embedding. In the sequence of steps in the algorithm, high regularities are forced in the structure of point sets. This lets us encounter beautiful mathematical structures on a 3-sphere and the symmetry group of finite points: the Hopf fibration of a 3-sphere and the Coxeter group of four-dimensional point groups. We also give an elementary and self-contained overview about these two mathematical topics. The main algorithm consists of five modules that are interesting in their own right. The algorithm is complicated and we provide rather pessimistic estimates. This algorithm, however, can be regarded as a big step forward to constructing a more efficient algorithm in higher dimensions. In the same vein, the last part is devoted to the extendability of the algorithm to higher dimensions. This part concludes with discussing implementability and geometric properties that the algorithm may imply.

Kongruenz ist ein Konzept der Geometrie, das die Gleichheit von Objekten in euklidischen Räumen beschreibt. Die erlaubten Operationen sind Rotationen und Translationen. Da Kongruenz eines der grundlegendsten Konzepte in der Geometrie ist, beschäftigen sich viele Wissenschaftler der algorithmischen Geometrie mit der Frage, ob der Test auf Kongruenz von zwei Punktmengen dem sogenannten "Fluch der Dimensionaltät" unterliegt. In dieser Arbeit entwickeln wir einen deterministischen Algorithmus für den Kongruenztest von Punktmengen in vierdimensionalen Räumen mit optimaler Laufzeit. Um die Bedeutung des Hauptalgorithmus im historischen Zusammenhang zu verstehen, beginnen wir mit einem Überblick über das zu Grunde liegende Rechenmodell. Weiterhin rezensieren wir die für Kongruenztestalgorithmen relevanten bisherigen Ergebnisse. Anschließend werden die ausschlaggebenden Bestandteile des neu entwickelten Algorithmus beschrieben. Dies beinhaltet insbesondere allgemeine vierdimensionale Drehungen, Winkel zwischen linearen Unterräumen und Plücker Einbettungen. Bei seiner Ausführung forciert der Algorithmus durch eine gezielte Fallunterscheidung in jedem Schritt mehr und mehr regelmäßige Strukturen in der Punktmenge. Dabei stoßen wir auf ansprechende mathematische Strukturen auf 3-Sphären und Spiegelungsgruppensymmetrien, die es zu verstehen und zu analysieren gilt. Dies beinhaltet die Hopf-Faserung einer dreidimsionalen Sphäre und die Coxeter Gruppe vierdimensionaler Spiegelungsgruppen. Aus diesem Grund geben wir eine einfache und geschlossene Übersicht über diese beiden Themen. Der Hauptalgorithmus besteht aus fünf Modulen, wobei jedes für sich einen anspruchsvollen Teilalgorithmus bildet. Das führt zu einem komplexen Hauptalgorithmus und zwingt uns zu pessimistischen Abschätzungen der Konstanten in der asymptotischen Laufzeit. Trotzdem kann dieser Algorithmus als ein erster, wichtiger Schritt zur Entwicklung von effizienten Algorithmen in höheren Dimensionen angesehen werden. Wir untersuchen mögliche Ansätze für diese Erweiterungen. Zum Abschluss folgt eine Diskussion über die Implementierbarkeit und über weitere mögliche geometrische Eigenschaften von vierdimensionalen Punktmengen, die der Algorithmus ausnutzt.