Polynomial-time algorithms for continuous metrics on atomic clouds of unordered points
arXiv:2207.08502 · doi:10.46793/match.91-1.079K
Abstract
The most fundamental model of a molecule is a cloud of unordered atoms, even without chemical bonds that can depend on thresholds for distances and angles. The strongest equivalence between clouds of atoms is rigid motion, which is a composition of translations and rotations. The existing datasets of experimental and simulated molecules require a continuous quantification of similarity in terms of a distance metric. While clouds of m ordered points were continuously classified by Lagrange's quadratic forms (distance matrices or Gram matrices), their extensions to m unordered points are impractical due to the exponential number of m! permutations. We propose new metrics that are continuous in general position and are computable in a polynomial time in the number m of unordered points in any Euclidean space of a fixed dimension n.
30 pages, 2 figures. The paper was published (with grayscale images) in the journal MATCH Communications in Mathematical and in Computer Chemistry, v.91 (2024), p.79-108, https://doi.org/10.46793/match.91-1.079K. This version includes color images. The latest file is at http://kurlin.org/projects/cloud-isometry-spaces/metrics-atomic-clouds.pdf
References in corpus (8)
- Smooth, exact rotational symmetrization for deep learning on point clouds
- Recognition of near-duplicate periodic patterns by continuous metrics with approximation guarantees
- Exactly computable and continuous metrics on isometry classes of finite and 1-periodic sequences
- The Gromov-Hausdorff distance between ultrametric spaces: its structure and computation
- Generic families of finite metric spaces with identical or trivial 1-dimensional persistence
- Simplexwise Distance Distributions for finite spaces with metrics and measures
- The Gromov--Hausdorff Distance between Simplexes and Two-Distance Spaces
- A Note on the Hausdorff Distance between Norm Balls and their Linear Maps