Testing two geometric objects for congruence, i.e., whether they are the same up to translations and rotations (and possibly reflections) is a fundamental question of geometry.
In the first part, I will survey the various algorithmic techniques that have been used since the 1970s to solve the problem for two n-point sets in two and three dimensions in O(n log n) time, such as string matching, planar graph isomorphism (Sugihara 1984), and the reduction technique of Atkinson (1987). In d dimensions, for small constant d, the best previous algorithm takes O(nceiling(d/3) log n) time (Brass and Knauer 2002). There is also a randomized Monte Carlo algorithm of Akutsu (1998) and Matoušek, which takes O(n(1+floor(d/2)/2 log n) time but which may miss to find a congruence, with small probability. I will review the involved techniques: the basic dimension reduction technique of Alt, Mehlhorn, Wagener, and Welzl (1998), the canonical forms of Akutsu (1998), the closest-pair graph of Matoušek, and the bipartite birthday paradox.
In the second part, I will introduce our recent algorithm for solving the 4-dimensional problem in O(n log n) time (joint work with Heuna Kim 2016). This algorithm will require the study of four-dimensional geometry, in particular the structure of four-dimensional rotations, Hopf fibrations, and the regular polytopes.
Brief bio: Günter Rote has been a Professor of Theoretical Computer Science at Freie Universität Berlin since 1999. He got his Ph.D. from the Technical University of Graz, Austria, in 1988 in the area of combinatorial optimization. By now, his main field of interest is computational geometry. He serves as a co-editor-in-chief of the Journal of Computational Geometry, one of the four journals that specialize in this field and the only one that provides fully open access. His interests are manifold. He has worked on motion-planning problems both with a view on practical applicability (robot motion) as well as theoretically (leading to the solution of the Carpenter's rule problem: Every polygonal chain can be continuously unfolded without self-crossings while keeping edge lengths fixed). He likes to enlist the help of computers in his research. He has investigated the growth rate of the number of different polyominoes as the number of cells increases (Klarner's constant). With the help of a supercomputer, a team that includes professor Rote is holding the current lower bound record, establishing rigorously for the first time that this constant is bigger than 4.