## Heuna Kim and Günter Rote:

# 1. Congruence testing of point sets in 4-space

to appear in:
*32st International Symposium on Computational
Geometry (SoCG 2016)*, Boston, June 2016. Editors: Sándor
Fekete and Anna Lubiw, Leibniz International Proceedings in
Informatics (LIPIcs), Schloss Dagstuhl-Leibniz-Zentrum für
Informatik, 2016. pp. 48:1–48:15. doi:10.4230/LIPIcs.SOCG.2016.48
# 2. Congruence testing of point sets in 4 dimensions

*Manuscript*, March 2016, 41 pages, arXiv:1603.07269 [cs.CC].
### Abstract

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`(`n`^{2}log `n`) and
`O`(n^{3/2}log `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.

Last update: August 24, 2017.