Congruence Testing of Point Sets in 4-Space.
Heuna Kim, Günter Rote · Universitätsbibliothek der FU Berlin Hochschulschriftenstelle u. Dokumentenserver · 2016
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.