Congruence testing of point sets in three and four dimensions
Presented by Prof. Günter ROTE
Type: Oral presentation
Track: Plenary Talk
I will survey algorithms for testing whether two given finite geometric objects are congruent. Under reasonable assumptions, the objects can be reduced to (labeled) point sets. I will introduce the two important techniques for congruence testing, namely dimension reduction and set pruning, and I will indicate how these techniques might lead for the first time to an algorithm for four dimensions with near-linear running time. As a by-product, one can find all symmetries of a geometric object, and thereby (in principle) obtain a classification of the finite symmetry groups of Euclidean space (the subgroups of O(4)).