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
  pdf file (gzipped)

2. Congruence testing of point sets in 4 dimensions

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


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.

  pdf file (gzipped)
  Video of a talk from the conference The Mathematics of Jiří Matoušek in Prague, July 2017 (including slides)
slides of a lecture at the CALDAM 2017 Pre-Conference School on Algorithms and Combinatorics in Goa, India, February 2017
other papers about this subject
Last update: August 24, 2017.