CGAL users discussion list

[Monique Teillaud <>]

Le 24/11/11 09:34, Andreas Fabri a écrit :
> On 24/11/2011 00:26, Juan Carlos Lopez Alfonso wrote:
> > 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?
> >
> > Best regards and thank in advance
> > Juan Carlos
>
> Hello,
>
> The word parallel planes makes ring a bell.
> If you insert the points one by one, and start with
> points on plane A, and later insert those of plane B,
> the first insertions of point in plane B, will
> have huge conflict zones: for the first point
> it are all "triangles" you have constructed so far.
> Inserting all points with the insert function
> that takes a range of points avoids that.

Yes. That's also why I asked about spatial sorting. The insert function 
taking a range of points actually uses spatial sorting (as documented).

> There might be an additional problem, namely that
> many orientation and insphere tests will be performed
> with exact arithmetic.

In fact I expect that the use of spatial sorting is going to reduce the 
number of calls to exact arithmetic.

> Can you send me your data set.
> I ask because we work on a solution for that.

indeed, having a closer look can be interesting.

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