Günter Rote:

Congruence testing of point sets in three and four dimensions—Results and techniques

Invited talk. In: Sixth International Conference on Mathematical Aspects of Computer and Information Sciences—MACIS 2015, November 2015, Editors: Ilias S. Kotsireas, Siegfried Rump, and Chee Yap, Lecture Notes in Computer Science, Vol. 9582, Springer-Verlag, 2016, pp. 50–59. doi:10.1007/978-3-319-32859-1_4


I will survey algorithms for testing whether two point sets are congruent, that is, equal up to an Euclidean isometry. I will introduce the important techniques for congruence testing, namely dimension reduction and pruning, or more generally, condensation. I will illustrate these techniques on the three-dimensional version of the problem, and indicate how they lead for the first time to an algorithm for four dimensions with near-linear running time (joint work with Heuna Kim). On the way, we will encounter some beautiful and symmetric mathematical structures, like the regular polytopes, and Hopf-fibrations of the three-dimensional sphere in four dimensions.

  pdf file (gzipped)
other papers about this subject
Last update: April 28, 2016.