Sources for verified Voronoi and power diagrams

Question

In the course of trying to implement algorithms for Voronoi and Laguerre diagrams, I realized I needed to verify if my implementation is working correctly using a point (or circle) configuration with a known Voronoi (or power) diagram.

I have not been successful in looking for datasets with known diagrams. Does anyone know a good source for these diagrams?

Answer 1

The most trivial pointsets are regular grid of points. They look innocent, but are the most difficult to handle in Voronoi/Laguerre codes because the Delaunay triangulation is non-unique, so they can be used to detect bugs in your code. They can be handled by adapted geometric predicates (see my publication [6] on geometric predicates and the references herein).

To detect bugs in my Voronoi/Laguerre diagram code in 2D and 3D [1], I used the following approach:

1. Compute the Voronoi/Laguerre diagram for a collection of pointsets (random) and test that the output of your code satisfies the empty ball property. For Voronoi, this means that the circumscribed circle(2d) or sphere(3d) of each Delaunay triangle does not contain any point. For Laguerre, there is a similar condition;

2. Compute the Voronoi/Laguerre diagram of random pointsets with a code that you trust [1] (if you trust me), [2],[3] (I trust them) and compare with the output of your code;

3. Add to the list of pointsets difficult ones. The difficult datasets are those that have cocyclic (2d) / cospheric (3d) points such as regular grids that I mentioned before. Note that when you got cocyclic / cospheric points, the Delaunay triangulation is non-unique (then the output of your code may differ as compared to other codes);

4. When all the weights are set to zero, the Laguerre diagram is a Voronoi diagram, then you can compare the output of your algorithms (if they mismatch, then both are probably wrong, like it happened to me).

I strongly recommend to use a continuous integration platform [4] to do automatic non-regression testing. Voronoi/Laguerre code is not very complicated (approx. 300 lines of code), but there are some gotchas/subtleties, in particular in the predicates for handling cocyclic points. Automatic daily tests (doing 1., 2., 3., 4. + Valgrind [5] memory test) allowed to detect several bugs in my own code.

[1] Geogram: http://alice.loria.fr/software/geogram/doc/html/index.html

[2] CGAL: http://www.cgal.org

[3] Tetgen:http://wias-berlin.de/software/tetgen/

[4] https://jenkins.io/

[5] http://valgrind.org/

[6] https://hal.inria.fr/hal-01225202