CGAL users discussion list

Ashwin Nanjappa wrote:
>  wrote:
>
> > 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.

> Edelsbrunner's (and Barry Joe's) paper is based on flipping. So, is 
> there a paper out there which talks about the CGAL's method of just 
> filling the hole which you just described? I'm also interested in 
> understanding the proof for CGAL's method.

It's a classic method.
See for instance

P.~J.~Green and R.~R.~Sibson.
Computing Dirichlet tessellations in the plane.
In {\em Comput. J.} 21:168--173, 1978.

A.~Bowyer.
Computing Dirichlet tesselations.
In {\em Comput. J.} 24:162--166, 1981.

best
        Monique Teillaud