How to construct Voronoi diagram on the sphere with CGAL easily?

Question

Firstly, I am new to CGAL, but program in C++ a lot. I would like to use CGAL to construct Voronoi diagram of points on the sphere. I have implemented one by myself for one of my research, but the data structure is not very generic, and I want to use more robust, industrial library like CGAL. From the doc of CGAL, it seems that we need to use 3D Delaunay triangulation combined with convex hull. In addition, I find a paper Robust and Efficient Delaunay Triangulations of Points on Or Close to a Sphere, which used CGAL as the base, but I could not find its code.

So anyone can provide an example about how to do this in CGAL? And does CGAL have any plan to support spherical Delaunay and Voronoi directly with more efficient algorithm?

Thanks in advance!

Answer 1

You can compute the Voronoi diagram of points on the sphere by first computing the convex hull [1], and then computing the facet normals. Multiply each of these normals by the radius of your sphere and you have the Voronoi vertices (according to [2]).

[1] http://doc.cgal.org/latest/Convex_hull_3/index.html

[2] http://www.qhull.org/html/qdelaun.htm