Efficient k-order voronoi diagram and 3d voronoi diagram in CGAL

Question

I'm having trouble in calculating k-order Voronoi diagram and 3d voronoi diagram in CGAL.

1. First, I want to calculate a k-order Voronoi diagram(k is the number of nearest neighbor) from given set of points(2d/3d).

   • As far as I know, there is a header file "k_delaunay.h" (code here) in CGAL demo ipelet folder. And it can calculate a k-order regular triangulation. And I believe I can convert regular triangulation to Delaunay triangulation.

   • However, from the code we can see the complexity is very high. I have tested 300k 2d points, and the actual run time for calculating k-order Voronoi diagram is not acceptable. So I wonder is there any other implementation of k-order Voronoi diagram in CGAL(the rest of my code is written in CGAL, so I really want to use the existing data structures)?

2. Also, since CGAL's voronoi diagram adapter only support 2D, is there any efficient way to convert 3D delaunay triangulation to 3D voronoi diagram?

Thanks!

Answer 1

Instead of k-order you can use a hierarchical cluster, i.e. a dendogram.