Complete Invariants of Atomic Clouds under Rigid Motion with Lipschitz Continuous Metrics in a Polynomial Time

A basic representation of any real molecule is a finite cloud of unordered atoms, many of which are chemically indistinguishable. A natural equivalence on point clouds in any metric space is defined by isometries that are distance-preserving transformations. In a Euclidean space, any isometry is a composition of translations, rotations, and reflections. If points are ordered, the isometry class of this cloud is uniquely determined by the matrix of all pairwise distances. If m points are unordered, a naive metric based on distance matrices needs exponentially many m! permutations. We define a complete invariant for n-dimensional clouds of m unordered points under rigid motion, which distinguishes all mirror images in R n. The key challenge was to design a distance on invariant values that is Lipschitz continuous under noise and computable in a polynomial time of cloud sizes, for a fixed dimension n.