CGAL users discussion list

Hi,

In the current CGAL implementation, there is no flip used for insertion 
in a 3D Delaunay triangulation.
The set of conflicting cells (ie cells whose circumsphere contains the 
new point) is computed, these cells are deleted and the hole is 
triangulated by simply joining the new point to all facets of the hole.

Flips could be used in 3D for insertions, but it is known that any 3D 
tetrahedralization can NOT always be converted to 3D Delaunay by flipping.

If I remember well, a relevant reference is
@article{es-itfwr-96
, author =      "H. Edelsbrunner and N. R. Shah"
, title =       "Incremental topological flipping works for regular 
triangulations"
, journal =     "Algorithmica"
, volume =      15
, year =        1996
, pages =       "223--241"
}
but there may be others.

Best
        Monique Teillaud

Ashwin Nanjappa wrote:
> Hi,
>
> I know that CGAL uses randomized incremental method for 3D Delaunay 
> triangulation. After point location, I was interested to see how the new 
> point is inserted and how the neighboring cells are affected by this. I 
> looked at the code, and it looks similar to the local flipping and 
> neighbor changes that I know from 2D Delaunay triangulation.
>
> Neither the CGAL code nor documentation mentions how this is exactly 
> done. Is there any paper/book that proves and details how the 
> incremental method works in 3D? Also, does this mean that any 3D 
> tetrahedralization can be converted to 3D Delaunay by flipping? I know 
> this is true for a planar point set, but is this true for 3D too?
>
> (Please excuse me if my query is a bit off-topic.)
>
> Regards,
> ~ash