TESTING APPROXIMATE SYMMETRY IN THE PLANE IS NP-HARD

Let A be a set of n points in the Euclidean plane. We would like to know its symmetry group. If the input points are given by rational coordinates (which is the normal case for a computer), then this problem degenerates to a trivial case. This is why we introduce the notion of approximate symmetry. In this notion, we consider a fixed tolerance factor epsilon and ask for the maximal symmetry group that is possible for a set A' consisting of n points in the epsilon-neighborhoods of the points in A, each point of A' belonging to a different point of A. We prove that the corresponding decision problem is NP-hard even when epsilon and the symmetry group we ask for is fixed. This is a rather surprising result, because a similar concept has been developed for approximate congruence recently and several polynomial algorithms are known for that related problem.