An algorithm for three-dimensional Voronoi S-network

Area of Science:

• Computational geometry
• Materials science
• Computational chemistry

Background:

• Analyzing void spaces in sphere ensembles is crucial for understanding material properties.
• Existing methods for Voronoi tessellations struggle with efficiency for large, heterogeneous datasets.

Purpose of the Study:

• To develop an efficient algorithm for computing 3D additively-weighted Voronoi diagrams of spheres.
• To create a data structure (Voronoi S-network) for exploring voids between spheres.
• To ensure the algorithm's scalability for large molecular systems.

Main Methods:

• Development of a novel algorithm for 3D Voronoi-Delaunay tessellation of spheres with varying radii.
• Construction of the Voronoi S-network, representing vertices and edges of Voronoi regions relative to sphere surfaces.
• Sequential determination of network sites by finding neighbors, starting from an initial site.

Main Results:

• The algorithm successfully calculates the 3D Voronoi-Delaunay tessellation for ensembles of spheres with different radii.
• The Voronoi S-network provides a framework for void exploration.
• Demonstrated linear time complexity (O(n)) for the algorithm, enabling efficient processing of large systems.

Conclusions:

• The developed algorithm is efficient and scalable for analyzing voids in large molecular systems represented by spheres.
• The Voronoi S-network is a valuable geometric construct for understanding inter-sphere spaces.
• The algorithm's applicability extends to various physical models composed of spherical elements.