Congruence testing for Point Sets in 4-Space
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
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
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.