CGAL users discussion list

[Olivier Devillers <>]

Le 1/11/14 6:55 PM, animo a écrit :

Dear Guys!  I tried to find out which kind of algorithm CGAL uses to calculate the delaunay triangulation in 3D and how the dual function works to get the voronoi diagram. I could only find out that in 2D it uses the flip algorithm.  Does anyone know how CGAL computes this things or where to find this information

This is not really part of the manual because it may change if we find algorithmic improvement.
The design and implementation history section of the 3d user manual gives some information.

Currently,

The algorithm is incremental,

if you use the Hierarchy in 2d or the fast location policy in 3D
it uses the Delaunay hierarchy to speed up point location,

If you insert many points at the same time it uses spartial sorting (BRIO insertion order)
to speed up point location for insertion of points.


You can find some information on expected running times there:
http://www-sop.inria.fr/members/Olivier.Devillers/EuroCG2012

--
Olivier Devillers, chercheur à