CGAL users discussion list

[Marc Glisse <>]

On Wed, 7 Oct 2015, Scherrer Daniel wrote:

> I experience huge differences in performance when triangulating in 6D. I 
> tested the following:
>
>         const int D = 6;
>         typedef CGAL::Epick_d<CGAL::Dimension_tag<D>> K;
>         typedef CGAL::Delaunay_triangulation<K> T;
>         for (int i = 0; i < 512; ++i){
>                 points.push_back(T::Point((i & 0x3), (i & 0xc) >> 2, (i & 0x30) 
> >> 4,
>                         (i & 0x40) >> 6, (i & 0x80) >> 7, (i & 0x100) >> 8));
>         }
>         T t(D);
>         t.insert(points.begin(), points.end());
>
> This takes about 12s on my PC.
>
> Then I tried the same but scaled the positions by 10 like this:

Try scaling by a power of 2 instead ;-)

>         ...
>         for (int i = 0; i < 512; ++i){
>                 points.push_back(T::Point((i & 0x3) * 10, ((i & 0xc) >> 2) * 10, ((i 
> & 0x30) >> 4) * 10,
>                         ((i & 0x40) >> 6) * 10, ((i & 0x80) >> 7) * 10, ((i & 
> 0x100) >> 8) * 10));
>         }
>
> And this takes more than 1 minute. The scaling itself does not seem to be the 
> problem. I tried different data sets which performed better or worse for no 
> obvious reason. I observed factors in computing time up to 30.
>
> Any idea what the triangulation performance could depend on?

Predicates are first evaluated using interval arithmetic (a pair of 
double). In usual non-degenerate cases, it is often sufficient to get the 
sign of the polynomial. In degenerate situations (when the result is 0), 
it usually fails because we don't know the sign of an interval containing 
zero, and the computation is done again using an exact but slow number 
type. Except in one case : when all the interval computations were lucky 
enough to be exact and the interval is thus just one point, 0. This can 
happen in particular when all the coordinates are very small integers.

--
Marc Glisse