Set Voronoi diagrams of 3D assemblies of aspherical particles

Abstract

Several approaches to quantitative local structure characterization for particulate assemblies, such as structural glasses or jammed packings, use the partition of space provided by the Voronoi diagram. The conventional construction for spherical mono-disperse particles, by which the Voronoi cell of a particle is that of its centre point, cannot be applied to configurations of aspherical or polydisperse particles. Here, we discuss the construction of a Set Voronoi diagram for configurations of aspherical particles in three-dimensional space. The Set Voronoi cell of a given particle is composed of all points in space that are closer to the surface (as opposed to the centre) of the given particle than to the surface of any other; this definition reduces to the conventional Voronoi diagram for the case of mono-disperse spheres. An algorithm for the computation of the Set Voronoi diagram for convex particles is described, as a special case of a Voronoi-based medial axis algorithm, based on a triangulation of the particles’ bounding surfaces. This algorithm is further improved by a pre-processing step based on morphological erosion, which improves the quality of the approximation and circumvents the problems associated with small degrees of particle–particle overlap that may be caused by experimental noise or soft potentials. As an application, preliminary data for the volume distribution of disordered packings of mono-disperse oblate ellipsoids, obtained from tomographic imaging, is computed.

Keywords:

• Set Voronoi diagram
• ellipsoid packings
• random close packing
• aspherical particles
• medial axes and surfaces
• Area Voronoi diagram
• navigation map
• skeleton by zone of influence

Acknowledgments

We thank Matthias Schröter for useful discussions and help, and Nikolai Medvedev, Dominique Jeulin, Claudia Redenbach and Adrian Sheppard for comments on the manuscript. We acknowledge support by the German Research Foundation (DFG) through the research group ‘Geometry and Physics of Spatial Random Systems’ under grant SCHR1148/3-1.

Notes

Note that this construction yields a double cover of the medial axis, as each point of the medial axis corresponds to at least two points on the bounding surface . The medial axis may also contain branch lines and points where each point is the image of three or more surface points and other lines or points that are the image of a cylindrical or spherical section of .

We have implemented the Set Voronoi algorithm using the program qhull for the computation of the conventional Point Voronoi diagram [91]. On current desktop computers, the computation of Point Voronoi diagrams of points is feasible. While the discussion in this section should apply generally to arbitrary particle shapes, we have studied the construction in detail only for the case of ellipsoidal particles.

For a point on a surface in 3D, an osculating sphere is a sphere centred in positive (negative) normal direction at a distance equal to the smaller of the positive (negative) radii of curvature of the surface at .