CGAL users discussion list

[Monique Teillaud <>]

Le 24/11/11 01:26, Juan Carlos Lopez Alfonso a écrit :
> Hi all:
>
> The documentation of Triangulation_3 says that constructions of Delaunay
> triangulations with more than 10^7 points is compute in 87.4 seconds. In
> my case, I have a set of points (3 500 000) in parallel planes and the
> computing time is much greater than this (hours). On the other hand, the
> same code in the same computer for a Triangulation_3 work very fast
> (minutes), but for Delaunay_triangulation_3 is very slow and throw an
> alloc exception (problem with memory).
>
> Please, could anyone explain me the reasons of this problems?

Hi,

We usually don't run benchmarks on Triangulation_3, because such 
triangulations don't seem to be very useful in practice, and the 
computed triangulation depends on the order in which points are inserted.

For Delaunay triangulations, 'degenerate' input data (which are more 
likely to occur when points lie in parallel planes) are expected to 
yield larger running times than random data sets.

That said, I am afraid that we cannot explain anything without knowing 
the conditions of your experiments at all, eg.
- did you compile in release mode?
- how much memory has your computer?
- did you use spatial sorting?
- ...

Best,

--
Monique Teillaud
INRIA Sophia Antipolis - Méditerranée
http://www.inria.fr/sophia/members/Monique.Teillaud/