CGAL中有效的k阶voronoi图和3d voronoi图

Question

我在CGAL中很难计算k阶Voronoi图和3d voronoi图。

1. 首先，从给定的点集(2d/3d)计算k阶Voronoi图(k是最近邻数)。

- As far as I know, there is a header file "k\_delaunay.h" (code [here](https://github.ugent.be/divhaere/cgal/blob/master/demo/CGAL_ipelets/include/CGAL_ipelets/k_delaunay.h)) 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)? 

​

1. 另外，由于CGAL的voronoi图适配器只支持2D，是否有任何有效的方法将3D delaunay三角剖分转换为3D voronoi图？

谢谢!

Answer 1

而不是k阶，您可以使用分层聚类，即树状图。