CGAL users discussion list

[Olivier Devillers <>]

Le 1/27/11 2:36 AM, Panagiotis Foteinos a écrit :
> Hello yall.
>
> Does anybody know what algorithm CGAL uses for removing a point in a 
> 3D Delaunay Triangulation? Has this algorithm been published?
>
> Thank you in advance,
> Panagiotis Foteinos

A small triangulation of the neighbors of the removed point is computed,
then the two triangulations are sewed along the link of the removed point

To ensure correctness you need unicity of the Delaunay triangulation 
which is ensured
by a perturbation scheme in case of degeneracies.




perturbation in 3d : http://hal.inria.fr/inria-00166710

2d removal : http://hal.inria.fr/inria-00433107/