CGAL users discussion list

[Olivier Devillers <>]

Le 11/24/11 9:22 AM, Juan Carlos Lopez Alfonso a écrit :
> Hi,
>
> In all cases I run my simulations in Release mode and my concern is 
> principally about the computing time. I am testing in a computer with 
> only 2 GB of RAM, but I will use a powerful computer in some days. For 
> this reason my concern is about the computing time.
>
> Even when my set of points are 'degenerate' (in parallel planes), Can 
> I always expect a result of Delaunay triangulations? How many time 
> will I approximately expect?
>
> You talk about the spatial sorting, and If I understand the meaning I 
> cant use spatial sorting, because I have a fixed set of points and are 
> in parallel planes.

If you insert your points one at a time, then a point location procedure 
is used to find where the new point
is added, if you insert all the points together using

dt.insert(begin,end)

where begin, end  gives a range of your points, then the points are 
reordered first to be inserted in an order
that improves the efficiency of the algorithm.



Concerning the degeneracies, if your points are in parallel (say 
horizontal)
planes but are not degenerated in one plane
(no cocircular points) you may also improve the efficiency by inserting
first one point above the highest plane and one point below the lowest plane
to avoid many coplanar faces on the convex hull.
If you really need it, you can remove these two points at the end
(it will be costly but I guess that you still be faster that without 
these two dummy points).

Olivier