Complete invariants of atomic clouds under rigid motion with Lipschitz continuous metrics in a polynomial time
This work addresses a fundamental problem in computational geometry and chemistry for representing molecules as unordered atomic clouds, though it is incremental as it builds on existing invariant theory with a focus on computational efficiency.
The paper tackled the problem of distinguishing unordered point clouds under rigid motions (isometries) in Euclidean space, which is computationally challenging due to exponential permutations, by defining a complete invariant that is Lipschitz continuous under noise and computable in polynomial time for fixed dimensions.
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.