We give a deterministic O(n log n)-time algorithm to decide if two n-point sets in 4-dimensional Euclidean space are the same up to rotations and translations.
A lower bound of Ω(n log n) has been known, and it has been conjectured that O(n log n) algorithms should exist for any fixed dimension. The best algorithms in d-space so far are are a deterministic algorithm by Brass and Knauer (2000) and a randomized Monte Carlo algorithm by Akutsu (1998). In 4-space, they take time O(n2log n) and O(n3/2log n), respectively.
Our algorithm exploits the geometric structure and the properties of 4-dimensional space, such as angles between planes, packing numbers, Hopf fibrations, Plücker coordinates, the classification of Coxeter groups, and rotations in 4-space.