CGAL users discussion list

[Daniel Duque <>]

On Monday 14 December 2009 09:58:18 Olivier Devillers wrote:
> the number of flipped edges could be n-4 after the insertion of the n-th
> point
> (it is the degree of the new inserted point [after insertion] minus 3)

From the manual:

Insertion is implemented by inserting in the triangulation, then performing a 
sequence of Delaunay flips. The number of flips is O(d) if the new vertex is 
of degree d in the new triangulation. For points distributed uniformly at 
random, insertion takes time O(1) on average. 

I guess, for "usual" applications one would get a O(1) time, which is great.

Best,

Daniel

-- 
http://debin.etsin.upm.es/~daniel