CGAL users discussion list

[Sylvain Pion <>]

Le 05/08/10 09:00, Ben Haller a écrit :
>    Hi all.  I've been using the Delaunay_d CGAL code for a while to do 3D 
> triangulations, which has worked very well.  I recently tried to step it up 
> to 4D and 5D triangulations, and things are not going so well.  CGAL is 
> causing a segfault because it is blowing through the maximum stack size 
> (which is 8 MB on OS X) around the 790th 5D point added to the triangulation. 
>  I tried giving it 16 MB of stack to give it more headroom, but then it just 
> blows through it a little later (around the 1250th point added).  It also 
> gets extremely slow at adding points compared to the 3D case; adding 16384 
> points in 3D takes just a couple of minutes total on my machine, but adding 
> 4D or 5D points gets to taking as long as a minute per point added (before it 
> causes the segfault).  I was hoping to add as many as 100,000 points to my 5D 
> triangulation, but clearly this is not going to work.
>
>    Is this known / expected?  Maybe doing triangulations in more than three dimensions is 
> inherently extremely difficult; but it kind of feels like the CGAL code might be switching 
> algorithms "under the hood" for>3 dimensions, and maybe the algorithm it 
> switches to is not so good.  Or have others been successful doing this kind of thing, and 
> there is something about the way I'm using CGAL that is causing problems?

Hi Ben,

The Delaunay_d code is indeed not the most efficient currently.
There is a new implementation in the works, derived from the
efficient Delaunay_triangulation_3.

You can get some timings in this paper :
http://www.loria.fr/~shornus/skeleton/del-skel.pdf

The new d-dim code might be available for early beta access,
ask Olivier Devillers if you are interested.

--
Sylvain