Abstract
Degree-k Voronoi domains of a periodic point set are concentric regions around a fixed centre consisting of all points in Euclidean space that have the centre as their k-th nearest neighbour. Periodic point sets generalise the concept of a lattice by allowing multiple points to appear within a unit cell of the lattice. Thus, periodic point sets model all solid crystalline materials (periodic crystals), and degree-k Voronoi domains of periodic point sets can be used to characterise the relative positions of atoms in a crystal from a fixed centre. The paper describes the first algorithm to compute all degree-k Voronoi domains up to any degree \(k\ge 1\) for any two or three-dimensional periodic point set.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Andrew, R.C., Salagaram, T., Chetty, N.: Visualising higher order Brillouin zones with applications. Eur. J. Phys. 38(3), 035501 (2017)
Anosova, O., Kurlin, V.: Introduction to periodic geometry and topology. arXiv:2103.02749 (2021)
Anosova, O., Kurlin, V.: An isometry classification of periodic point sets. In: Lindblad, J., Malmberg, F., Sladoje, N. (eds.) DGMM 2021. LNCS, vol. 12708, pp. 229–241. Springer, Cham (2021). https://doi.org/10.1007/978-3-030-76657-3_16
Anosova, O., Kurlin, V.: Algorithms for continuous metrics on periodic crystals. arXiv:2205.15298 (2022)
Anosova, O., Kurlin, V.: Density functions of periodic sequences. In: Discrete Geometry and Mathematical Morphology (2022)
Bright, M., Cooper, A., Kurlin, V.: Welcome to a continuous world of 3-dimensional lattices. arxiv:2109.11538 (2021)
Bright, M.J., Cooper, A.I., Kurlin, V.A.: Geographic-style maps for 2-dimensional lattices. Acta Crystallographica Sect. A 79(1), (2023)
Chan, T.M.: Random sampling, halfspace range reporting, and construction of \(k\)-levels in three dimensions. SIAM J. Comput. 30(2), 561–575 (2000)
Dolbilin, N., Huson, D.: Periodic Delone tilings. Per. Math. Hung. 34, 57–64 (1997). https://doi.org/10.1023/A:1004272423695
Edelsbrunner, H., Garber, A., Ghafari, M., Heiss, T., Saghafian, M.: On angles in higher order brillouin tessellations and related tilings in the plane. arxiv:2204.01076
Edelsbrunner, H., Garber, A., Ghafari, M., Heiss, T., Saghafian, M., Wintraecken, M.: Brillouin zones of integer lattices and their perturbations. arxiv:2204.01077
Edelsbrunner, H., Heiss, T., Kurlin, V., Smith, P., Wintraecken, M.: The density fingerprint of a periodic point set. In: Symposium on Computational Geometry, pp. 32:1–32:16 (2021)
Edelsbrunner, H., Iglesias-Ham, M.: On the optimality of the FCC lattice for soft sphere packing. SIAM J. Discrete Math. 32(1), 750–782 (2018)
Edelsbrunner, H., Osang, G.: A simple algorithm for higher-order Delaunay mosaics and alpha shapes. Algorithmica, 1–19 (2022). Springer
Edelsbrunner, H., Seidel, R.: Voronoi diagrams and arrangements. Discrete Comput. Geom. 1(1), 25–44 (1986). https://doi.org/10.1007/BF02187681
Hart, G., Jorgensen, J., Morgan, W., Forcade, R.: A robust algorithm for k-point grid generation and symmetry reduction. J. Phys. Commun. 3(6), 065009 (2019)
Kurlin, V.: Complete invariants for finite clouds of unlabeled points. arxiv:2207.08502
Kurlin, V.: A complete isometry classification of 3D lattices. arxiv:2201.10543
Kurlin, V.: Exactly computable and continuous metrics on isometry classes of finite and 1-periodic sequences. arXiv:2205.04388 (2022)
Kurlin, V.A.: Mathematics of 2-dimensional lattices. Found. Comput. Math. (to appear)
Mosca, M., Kurlin, V.: Voronoi-based similarity distances between arbitrary crystal lattices. Cryst. Res. Technol. 55(5), 1900197 (2020)
Nguyen, P.Q., Stehlé, D.: Low-dimensional lattice basis reduction revisited. ACM Trans. Algorithms 5(4) (2009). https://doi.org/10.1145/1597036.1597050
Osang, G., Rouxel-Labbé, M., Teillaud, M.: Generalizing CGAL periodic Delaunay triangulations. In: European Symposium on Algorithms, pp. 75:1–75:17 (2020)
Smith, P., Kurlin, V.: Families of point sets with identical 1D persistence. arxiv:2202.00577 (2022)
TLP. https://www.doitpoms.ac.uk/tlplib/brillouin_zones/index.php
Torda, M., Goulermas, J.Y., Kurlin, V., Day, G.M.: Densest plane group packings of regular polygons, Phys. Rev. E 106(5), 054603 (2022). APS
Vriza, A., et al.: Molecular set transformer: attending to the co-crystals in the Cambridge structural database. Digital Discovery (2022)
Widdowson, D., Kurlin, V.: Resolving the data ambiguity for periodic crystals. In: Advances in Neural Information Processing Systems (NeurIPS), vol. 35 (2022)
Widdowson, D., Mosca, M., Pulido, A., Cooper, A., Kurlin, V.: Average minimum distances of periodic sets. MATCH Commun. Math. Comput. Chem. 87, 529–559 (2022)
Zhu, Q., et al.: Analogy powered by prediction and structural invariants. J. Am. Chem. Soc. 144, 9893–9901 (2022)
Author information
Authors and Affiliations
Corresponding authors
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2022 The Author(s), under exclusive license to Springer Nature Switzerland AG
About this paper
Cite this paper
Smith, P., Kurlin, V. (2022). A Practical Algorithm for Degree-k Voronoi Domains of Three-Dimensional Periodic Point Sets. In: Bebis, G., et al. Advances in Visual Computing. ISVC 2022. Lecture Notes in Computer Science, vol 13598. Springer, Cham. https://doi.org/10.1007/978-3-031-20713-6_29
Download citation
DOI: https://doi.org/10.1007/978-3-031-20713-6_29
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-031-20712-9
Online ISBN: 978-3-031-20713-6
eBook Packages: Computer ScienceComputer Science (R0)