# An Algorithm Searching for Point Subsets with Applications to the Analysis of the Atomic Structure of Modelled Clusters

D.S. Krupyanskiy, A.D. FofanovThis article presents the results of efforts to develop a method for analyzing the atomic structure of clusters obtained in computer simulations. The method is based on looking for coordination polyhedra in the clusters and constructing a graph to describe their relative positions. It requires us to calculate topological invariants of this graph in order to compare them with the physical and chemical properties of the corresponding clusters. To find coordination polyhedra, we propose an algorithm searching for point subsets using a template. We apply the method to clusters of various form, structure, and composition. We suggest several simple graph invariants reflecting the structure of clusters. The algorithm is implemented in a program which enables us to find coordination polyhedra, construct the corresponding graph, and calculate the invariants.Full text

- Keywords
- searching for point subsets; atomic structure modelling; structure analysis.
- References
- 1. Anfilogov V.N., Bykov V.N., Osipov A.A. Silikatnye rasplavy [The Silicate Melts]. Moscow, 2005. 357 p.

2. Koroleva O.N., Tupitsyn A.A., Bychinskiy V.A. [Physicochemical Model of Sodium Silicate Melt and Thermodynamics of Q^n-species]. Bulletin of the South Ural State University. Series 'Chemistry', 2012, no. 36, pp. 39-44. (in Russian)

3. Taracheva I.A., Shchedrin B.M. [Solution of a Problem of Comparison of Point Sets for Common Subsets Detection]. Kristallografiya, 1994, vol. 39, no. 4, pp. 586-589. (in Russian)

4. Voloshin B.P., Medvedev N.N., Naberukhin YU.I., Geiger A., Klene M. Radial Distribution Functions of Atoms and Voids in Large Computer Models of Water. Journal of Structural Chemistry, 2005, vol. 46, no. 3, pp. 438-445. DOI: 10.1007/s10947-006-0122-1

5. Naberukhin YU.I., Voloshin B.P. Structure of Large Noncrystalline Lennard-Jones Models. Journal of Structural Chemistry, 2006, vol. 47, supplement, pp. 126-140. DOI: 10.1007/s10947-006-0387-4

6. Medvedev N.N. Metod Voronogo-Delone v issledovanii struktury nekristallicheskikh sistem [The Voronoi-Delaunay Method for Non-crystalline Structures]. Novosibirsk, 2000. 214 p.

7. Anikeenko A.V., Medvedev N.N. Polytetrahedral Nature of the Dense Disordered Packings of Hard Spheres. Physical Review Letters, 2007, 98(23), 235504(4).

8. Anikeenko A.V., Gavrilova M.L., Medvedev N.N. Shapes of Delaunay Simplixes and Structural Analisis of Hard Sphere Packings. Generalized Voronoi Diagram: A Geometry-Based Approach to Computational Intelligence, 2008, SCI vol. 158, pp. 13-45. DOI: 10.1007/978-3-540-85126-4_2

9. Zefirov N.S. Primenenie teorii grafov v khimii [Graph Theory Application for Chemistry]. Novosibirsk, Nauka, 1988. 306 p.

10. King R.B. Chemical Applications of Topology and Graph Theory, New York, Elsevier, 1983.