Abstract
The fundamental model of a periodic structure is a periodic point set up to rigid motion or isometry. Our recent paper in SoCG 2021 defined isometry invariants (density functions), which are complete in general position and continuous under perturbations. This work introduces much faster isometry invariants (average minimum distances), which are also continuous and distinguish some sets that have identical density functions. We explicitly describe the asymptotic behaviour of the new invariants for a wide class of sets including non-periodic. The proposed near linear time algorithm processed a dataset of hundreds of thousands of real structures in a few hours on a modest desktop.
Introduction: The Challenge of Periodic Representation
In crystallography and materials science, representing a periodic structure is surprisingly complex. Traditionally, a "unit cell" and a "motif" (a set of points within that cell) are used. However, this representation is highly ambiguous: the same physical crystal can be described by infinitely many different unit cells.
Furthermore, standard descriptors like symmetry groups are discontinuous. A tiny vibration or measurement error in an atom's position can cause a crystal's symmetry group to "jump" from one category to another, making it nearly impossible to quantify how similar two "almost identical" structures are. While newer "density functions" solved the continuity problem, they were computationally expensive ($O(mk^3)$). This research seeks a descriptor that is continuous, fast to compute, and powerful enough to distinguish complex structures.
Methodology: Average Minimum Distances (AMD)
The authors introduce Average Minimum Distances (AMD) as a robust "fingerprinting" method. For a periodic point set $S$ with a motif of $m$ points, the AMD is calculated through a three-step process:
- Neighbor Search: For each point $p_i$ in the motif, the algorithm finds its $k$ nearest neighbors in the infinite periodic set.
- Distance Matrix: It records the distances $d_{ij}$ to these $k$ neighbors, creating an $m \times k$ matrix.
- Averaging: The $k$-th AMD value is the average of the $k$-th column of this matrix.
Key Innovations
- Near-Linear Algorithm: By using $n$-d trees and exploiting the periodic nature of the data, the authors achieve a complexity of $O(km \log(km))$, making it orders of magnitude faster than previous continuous invariants.
- Asymptotic Behavior: The paper proves that as $k \to \infty$, $AMD_k$ grows at a predictable rate proportional to $\sqrt[n]{k}$, where $n$ is the dimension. This allows for the definition of a "point packing coefficient" as a stable structural signature.
- Continuity: AMDs are rigorously proven to be Lipschitz continuous under the "bottleneck distance," ensuring that small structural changes result in only small changes to the AMD values.
Results and Discussion
The algorithm was evaluated on massive, real-world datasets, including the Cambridge Structural Database (CSD). The researchers processed a subset of 228,994 organic structures in less than 52 minutes on a standard desktop. For a single structure, computing $AMD_{100}$ takes approximately 10–13 milliseconds.
AMDs successfully distinguished five different experimental phases (polymorphs) of the T2 molecule, which are often difficult to separate using standard density-based metrics. This high resolution, combined with extreme speed, allowed for the creation of the largest-ever map of organic crystals, visualized as a TreeMap where similar geometries are grouped together regardless of chemical composition.
Conclusion
The AMD framework provides a mathematically robust and computationally efficient solution for comparing periodic structures. By canonicalizing structures without needing a discontinuous reduction step, it enables the rapid mapping of chemical space. Future work aims to prove the mathematical completeness of AMDs for all non-isometric periodic sets and to more deeply integrate chemical labels into the geometric framework.
Summary updated