Many physical systems can be studied as collections of particles embedded in space, often evolving in time. Natural questions arise concerning how to characterize these arrangements-are they ordered or disordered? If they are ordered, how are they ordered and what kinds of defects do they possess? Voronoi tessellations, originally introduced to study problems in pure mathematics, have become a powerful and versatile tool for analyzing countless problems in pure and applied physics. We explain the basics of Voronoi tessellations and the shapes that they produce and describe how they can be used to characterize many physical systems.

VORO++ is a software library written in C++ for computing the Voronoi tessellation, a technique in computational geometry that is widely used for analyzing systems of particles. VORO++ was released in 2009 and is based on computing the Voronoi cell for each particle individually. Here, we take advantage of modern computer hardware, and extend the original serial version to allow for multithreaded computation of Voronoi cells via the OpenMP application programming interface. We test the performance of the code, and demonstrate that it can achieve parallel efficiencies greater than 95% in many cases. The multithreaded extension follows standard OpenMP programming paradigms, allowing it to be incorporated into other programs. We provide an example of this using the VoroTop software library, performing a multithreaded Voronoi cell topology analysis of up to 102.4 million particles. Program summary: Program title: VORO++ CPC Library link to program files: https://doi.org/10.17632/tddc4w4zkk.1 Developer's repository link: https://github.com/chr1shr/voro Licensing provisions: BSD 3-clause (with LBNL modification) Programming language: C++ External routines/libraries: OpenMP Nature of problem: Multithreaded computation of the Voronoi tessellation in two and three dimensions Solution method: The VORO++ library is built around several C++ classes that can be incorporated into other programs. The two largest components are the container. classes that spatially sort input particles into a grid-based data structure, allowing for efficient searches of nearby particles, and the voronoicell. classes that represent a single Voronoi cell as an arbitrary convex polygon or polyhedron. The Voronoi cell for each particle is built by considering a sequence of plane cuts based on neighboring particles, after which many different statistics (e.g. volume, centroid, number of vertices) can be computed. Since each Voronoi cell is calculated individually, the Voronoi cells can be computed using multithreading via OpenMP.