How does voro++ deal with vertex issue in weighted voronoi volume calculation?

[CalvinZQCui]

Hi Prof. Rycroft,

I'm a user of voro++. This is really a helpful software especially in calculating weighted voronoi volume.

However, now I have one question regarding how it deals with the degenerated conditions. As I can see from the description, voro++ adopts Laguerre tessellation method to do the weighted voronoi volume calculation. But as we know, Laguerre tessellation will sometimes inevitably lead to some vertex errors and degenerated issues, so I'm curious how voro++ deals with these issues.

The manual indicates that it will set a numerical tolerance to avoid float-point precision issue, but I'm not sure if this way also applies to the vertex error caused by Laguerre tessellation.

Thank you so much for your time and attention. Look forward to hearing from you.

[chr1shr]

Thanks for your interest in Voro++. The issues with vertex errors are the same even for the original Voronoi tessellation—I don't think that there is anything different about this for the Laguerre tessellation.*

For a random arrangement of points, the Voronoi cells (either regular or Laguerre) will have vertices of order 3. But if the points are precisely aligned then it is possible for the vertices to be order 4 or higher.

Within Voro++, each Voronoi cell is initialized to fill the entire domain, and then for every neighboring particle a plane cut is applied to reduce the cell volume. Once all neighboring particles have been considered, then Voronoi cell is complete.

Usually, the cutting planes intersect edges of the partially computed Voronoi cell, resulting in new vertices of order 3. But in some cases, the cutting planes may precisely align with a vertex, which may create higher order vertices.

Numerically, Voro++ detects this alignment when the Voronoi cell is within a small tolerance of the cutting plane. In the development version of Voro++, this tolerance is set to proportional to the container dimensions.

In general, it works quite well, and there are some examples on the website, degenerate.cc and degenerate2.cc, that demonstrate the ability to form high-order vertices. But due to the unavoidable rounding errors of floating point numbers, slightly perturbed input may result in different vertex topology. The order in which the plane cuts are considered may also result in different vertex topology.

Furthermore, a substantial limitation of this is that each Voronoi cell is computed independently. This has major benefits in some applications, since it allows Voronoi cell computation to be multithreaded. But because each Voronoi cell is subject to different rounding error, there is no guarantee that the vertex topology of one Voronoi cell is consistent with a neighbor.

Depending on what you want to do, you might want to consider the following:

• Different software and algorithms can compute the entire Voronoi tessellation as a single computational object. By doing this, you can ensure that the overall vertex topology between cells will be consistent. You could look at Qhull or CGAL.

• It is possible to compute Voronoi cells using exact arithmetic. This could be done with an exact rational representation of numbers, such as those in GMP. I have tried modifying Voro++ to use this in the past, and it can be done in principle, but it requires a substantial overhaul of the code internals. Plus the computations are far slower than using standard floating point arithmetic.

You might also find the work of Lazar and collaborators useful. They show that if you perturb an ideal Voronoi cell (e.g. a rhombic dodecahedron arising from an FCC packing) then you will get a family of perturbed Voronoi cell topologies that appear in statistically reproducible fractions. Emanuel Lazar has a software package VoroTop that uses this for particle analysis. This picture can be really useful, since it sidesteps the issues of rounding error, and provides a framework for dealing with the perturbed cells.

* There are other issues (not about vertex accuracy) that are specific to the Laguerre tessellation. For some choices of radii, it is possible that some cells will completely disappear, e.g. if you have a particle with a small radius next to some particles with giant radii. If Voro++ detects this, then that cell is omitted from the output files. Within the C++ API, the compute_cell function returns false if the Voronoi cell was completely deleted.