Medvedev N N, Voloshin V P, Luchnikov V A, Gavrilova M L
Institute of Chemical Kinetics and Combustion SB RAS, Novosibirsk, Russia.
J Comput Chem. 2006 Nov 15;27(14):1676-92. doi: 10.1002/jcc.20484.
The paper presents an algorithm for calculating the three-dimensional Voronoi-Delaunay tessellation for an ensemble of spheres of different radii (additively-weighted Voronoi diagram). Data structure and output of the algorithm is oriented toward the exploration of the voids between the spheres. The main geometric construct that we develop is the Voronoi S-network (the network of vertices and edges of the Voronoi regions determined in relation to the surfaces of the spheres). General scheme of the algorithm and the key points of its realization are discussed. The principle of the algorithm is that for each determined site of the network we find its neighbor sites. Thus, starting from a known site of the network, we sequentially find the whole network. The starting site of the network is easily determined based on certain considerations. Geometric properties of ensembles of spheres of different radii are discussed, the conditions of applicability and limitations of the algorithm are indicated. The algorithm is capable of working with a wide variety of physical models, which may be represented as sets of spheres, including computer models of complex molecular systems. Emphasis was placed on the issue of increasing the efficiency of algorithm to work with large models (tens of thousands of atoms). It was demonstrated that the experimental CPU time increases linearly with the number of atoms in the system, O(n).
本文提出了一种用于计算不同半径球体集合的三维Voronoi-Delaunay镶嵌的算法（加权Voronoi图）。该算法的数据结构和输出旨在探索球体之间的空隙。我们开发的主要几何结构是Voronoi S网络（相对于球体表面确定的Voronoi区域的顶点和边的网络）。讨论了算法的总体方案及其实现的关键点。该算法的原理是对于网络中每个确定的位点，找到其相邻位点。因此，从网络的一个已知位点开始，我们依次找到整个网络。基于某些考虑可以很容易地确定网络的起始位点。讨论了不同半径球体集合的几何性质，指出了算法的适用条件和局限性。该算法能够处理各种物理模型，这些模型可以表示为球体集合，包括复杂分子系统的计算机模型。重点讨论了提高算法处理大型模型（数万个原子）效率的问题。结果表明，实验CPU时间与系统中的原子数呈线性增加，即O(n)。
