Document Open Access Logo

The Density Fingerprint of a Periodic Point Set

Authors Herbert Edelsbrunner , Teresa Heiss , Vitaliy Kurlin , Philip Smith , Mathijs Wintraecken

PDF
Thumbnail PDF

File

LIPIcs.SoCG.2021.32.pdf
  • Filesize: 3.07 MB
  • 16 pages

Document Identifiers

Author Details

Herbert Edelsbrunner
  • IST Austria (Institute of Science and Technology Austria), Klosterneuburg, Austria
Teresa Heiss
  • IST Austria (Institute of Science and Technology Austria), Klosterneuburg, Austria
Vitaliy Kurlin
  • Department of Computer Science, University of Liverpool, UK
Philip Smith
  • Department of Computer Science, University of Liverpool, UK
Mathijs Wintraecken
  • IST Austria (Institute of Science and Technology Austria), Klosterneuburg, Austria

Funding

  • Edelsbrunner, Herbert: ERC Horizon 2020 "Alpha Shape Theory Extended", no. 788183; FWF "Wittgenstein Prize", no. Z 342-N31; FWF DFG TRR 109 "Discretization in Geometry and Dynamics", no. I 02979-N35.
  • Heiss, Teresa: ERC Horizon 2020 "Alpha Shape Theory Extended", no. 788183.
  • Kurlin, Vitaliy: EPSRC grant "Application-driven Topological Data Analysis" (EP/R018472/1).
  • Smith, Philip: Leverhulme Research Centre for Functional Materials Design at the University of Liverpool, UK.
  • Wintraecken, Mathijs: the European Union’s Horizon 2020 research and innovation programme under the Marie Skłodowska-Curie grant agreement No. 754411.

Acknowledgements

The authors thank Janos Pach for insightful discussions on the topic of this paper, Morteza Saghafian for finding the one-dimensional counterexample mentioned in Section 5, and Larry Andrews for generously sharing his crystallographic perspective.

Cite AsGet BibTex

Herbert Edelsbrunner, Teresa Heiss, Vitaliy Kurlin, Philip Smith, and Mathijs Wintraecken. The Density Fingerprint of a Periodic Point Set. In 37th International Symposium on Computational Geometry (SoCG 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 189, pp. 32:1-32:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
https://doi.org/10.4230/LIPIcs.SoCG.2021.32

Abstract

Modeling a crystal as a periodic point set, we present a fingerprint consisting of density functions that facilitates the efficient search for new materials and material properties. We prove invariance under isometries, continuity, and completeness in the generic case, which are necessary features for the reliable comparison of crystals. The proof of continuity integrates methods from discrete geometry and lattice theory, while the proof of generic completeness combines techniques from geometry with analysis. The fingerprint has a fast algorithm based on Brillouin zones and related inclusion-exclusion formulae. We have implemented the algorithm and describe its application to crystal structure prediction.

Subject Classification

ACM Subject Classification
  • Theory of computation → Computational geometry
Keywords
  • Lattices
  • periodic sets
  • isometries
  • Dirichlet-Voronoi domains
  • Brillouin zones
  • bottleneck distance
  • stability
  • continuity
  • crystal database

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Lawrence C. Andrews, Herbert J. Bernstein, and G.A. Pelletier. A perturbation stable cell comparison technique. Acta Crystallographica, A36(2):248-252, 1980. URL: https://doi.org/10.1107/S0567739480000496.
  2. Franz Aurenhammer. Power diagrams: properties, algorithms and applications. SIAM Journal on Computing, 16(1):78-96, 1987. URL: https://doi.org/10.1137/0216006.
  3. David Avis, Binay K. Bhattacharya, and Hiroshi Imai. Computing the volume of the union of spheres. The Visual Computer, 3(6):323-328, 1988. URL: https://doi.org/10.1007/BF01901190.
  4. Mireille Boutin and Gregor Kemper. On reconstructing n-point configurations from the distribution of distances or areas. Advances in Applied Mathematics, 32(4):709-735, 2004. URL: https://doi.org/10.1016/S0196-8858(03)00101-5.
  5. James A. Chisholm and Sam Motherwell. Compack: a program for identifying crystal structure similarity using distances. Journal of Applied Crystallography, 38(1):228-231, 2005. URL: https://doi.org/10.1107/S0021889804027074.
  6. Nikolai P. Dolbilin, Jeffrey C. Lagarias, and Marjorie Senechal. Multiregular point systems. Discrete & Computational Geometry, 20(4):477-498, 1998. URL: https://doi.org/10.1007/PL00009397.
  7. Herbert Edelsbrunner. Algorithms in Combinatorial Geometry, volume 10 of Monographs in Theoretical Computer Science. An EATCS Series. Springer-Verlag Berlin Heidelberg, 1987. URL: https://doi.org/10.1007/978-3-642-61568-9.
  8. Herbert Edelsbrunner and Ping Fu. Measuring space filling diagrams and voids. In Molecular Biophysic Report UIUC-BI-MB-94-01. University of Illinois at Urbana-Champaign, 1994. Google Scholar
  9. Herbert Edelsbrunner and Mabel Iglesias-Ham. Multiple covers with balls I: inclusion-exclusion. Computational Geometry, 68:119-133, 2018. URL: https://doi.org/10.1016/j.comgeo.2017.06.014.
  10. Gemma de la Flor, Danel Orobengoa, Emre Tasci, Juan M. Perez-Mato, and Mois I. Aroyo. Comparison of structures applying the tools available at the Bilbao crystallographic server. Journal of Applied Crystallography, 49(2):653-664, 2016. URL: https://doi.org/10.1107/S1600576716002569.
  11. F. Alberto Grünbaum and Calvin C. Moore. The use of higher-order invariants in the determination of generalized patterson cyclotomic sets. Acta Crystallographica, A51(3):310-323, 1995. URL: https://doi.org/10.1107/S0108767394009827.
  12. Paul Lemke, Steven S. Skiena, and Warren D. Smith. Reconstructing sets from interpoint distances. Springer Berlin Heidelberg, 2003. URL: https://doi.org/10.1007/978-3-642-55566-4_27.
  13. Clare F. Macrae, Paul R. Edgington, Patrick McCabe, Elna Pidcock, Greg P. Shields, Robin Taylor, Matthew Towler, and Jacco van de Streek. Mercury: visualization and analysis of crystal structures. Journal of Applied Crystallography, 39(3):453-457, 2006. URL: https://doi.org/10.1107/S002188980600731X.
  14. Phong Q. Nguyen and Damien Stehlé. Low-dimensional lattice basis reduction revisited. In "Proceedings of the 6th International Algorithmic Number Theory Symposium", pages 338-357, 2004. URL: https://doi.org/10.1007/978-3-540-24847-7_26.
  15. Paul Niggli. Krystallographische und strukturtheoretische Grundbegriffe, volume 1 of Handbuch der Experimentalphysik, Band 7. Akademische Verlagsgesellschaft mbH, 1928. Google Scholar
  16. Linus Pauling and Maple D. Shappell. 8. The crystal structure of bixbyite and the c-modification of the sesquioxides. Zeitschrift für Kristallographie - Crystalline Materials, 75(1):128-142, 1930. URL: https://doi.org/10.1515/zkri-1930-0109.
  17. Angeles Pulido et al. Functional materials discovery using energy-structure-function maps. Nature, 543(7647):657-664, 2017. URL: https://doi.org/10.1038/nature21419.
  18. Marjorie Senechal. A point set puzzle revisited. European Journal of Combinatorics, 29(8):1933-1944, 2008. URL: https://doi.org/10.1016/j.ejc.2008.01.013.
  19. Philip Smith. Density functions of a periodic set in C++, 2020. URL: https://github.com/Phil-Smith1/Density_Functions.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact