So, the ever-arrogant programmer that I am recently discovered that Boost.Polygon does not support 3D Voronoi diagrams. This simply cannot be!

My proposal is relatively straight-forward, we add a 3D Delaunay triangulator and use that to implement the Voronoi tessellation for a given set of points.

Now, before any code is written we must first decide a couple of things.

Namely, we need to discuss the algorithm of the Delaunay triangulator.

I propose that we eschew the perturbative method as outlined in the Simulation of Simplicity and instead opt to handle the case of a point being on the face of a tetrahedron directly. This implies that the algorithm we will use is an incremental construction algorithm with a jump-and-walk approach. These are relatively straight-forward to implement and because of that, likely easier to maintain by future developers.

From there, we can work on making it parallel and the using our underlying triangulation, we can develop the Voronoi tessellation from that.

Also, support for arbitrary precision seems mandatory and is now an industry standard.

Unfortunately, this problem is not uniquely solved. There are tons of libraries out there that already do this kind of stuff but they don't interface as directly with Boost. I suppose the overall goal of this library addition would be to give the same functionality but with a better way of working within the current Boost ecosystem.

Thoughts?

- Chris