On determining the congruence of point sets in d dimensions

This paper considers the following problem: given two point sets A and B (\A\ = \B\ = n) in d dimensional Euclidean space, determine whether or not A is congruent to B. This paper presents an O(n((d-1)/2) log n) time randomized algorithm. The birthday paradox, which is well-known in combinatorics, is used effectively in this algorithm. Although this algorithm is Monte-Carlo type (i.e., it may give a wrong result), this improves a previous O(n(d-2) logn) time deterministic algorithm considerably. This paper also shows that if d is not bounded, the problem is at least as hard as the graph isomorphism problem in the sense of the polynomiality. Several related results are described too. (C) 1998 Elsevier Science B.V.