Congruence Testing of Point Sets in 4 Dimensions

Abstract

Congruence between two n-point sets in 4 dimension can be checked in O(n log n) time. On the way to establishing this result, we revisit several parts of 4-dimensional geometry, such as angles and distances between planes, Hopf fibrations, and Coxeter groups.

41 pages, 6 figures. This is the full version accompanying our paper "Congruence testing of point sets in 4-space" that is to apper at the 32st International Symposium on Computational Geometry (SoCG 2016), (LIPIcs proceedings series)