ON THE GEOMETRIC GRAPH ISOMORPHISM-PROBLEM

Given two finite subsets A, B of R-k (of C-k) we test in time (e(k4) n l)(O(1)) whether there exists an isometry f of R-k (resp. of C-k) such that f(A) = B where n is the maximum of the cardinalities of A and B, and I is the maximum size of a vector belonging to A boolean OR B. In contrast to the trivial (n(k) l)(O(1))-test, our algorithm is polynom ial time not only for a fixed Fe bur also for k = O((4) root log n). ( C) 1997 Published by Elsevier Science B.V.