dD Delaunay triangulation highly inefficient

classic Classic list List threaded Threaded
4 messages Options
Reply | Threaded
Open this post in threaded view
|

dD Delaunay triangulation highly inefficient

Ben Haller
  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?

Ben Haller
McGill University


--
You are currently subscribed to cgal-discuss.
To unsubscribe or access the archives, go to
https://lists-sop.inria.fr/wws/info/cgal-discuss

Reply | Threaded
Open this post in threaded view
|

Re: dD Delaunay triangulation highly inefficient

Sylvain Pion
Administrator
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

--
You are currently subscribed to cgal-discuss.
To unsubscribe or access the archives, go to
https://lists-sop.inria.fr/wws/info/cgal-discuss

Reply | Threaded
Open this post in threaded view
|

Re: dD Delaunay triangulation highly inefficient

Ben Haller
On Aug 5, 2010, at 9:25 AM, Sylvain Pion wrote:

> 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.

  I see.  Good to have the problem confirmed, thanks.  I probably won't pursue the early beta; I have a short timeframe for completing this project, and so I have a low tolerance for risk.  I've got an alternative approach that I will pursue instead.

  I would like to know when this new algorithm makes it into the official CGAL distribution, though.  Will that be announced on this list, or do I need to subscribe to something else?

  Thanks!

Ben Haller
McGill University



--
You are currently subscribed to cgal-discuss.
To unsubscribe or access the archives, go to
https://lists-sop.inria.fr/wws/info/cgal-discuss

Reply | Threaded
Open this post in threaded view
|

Re: dD Delaunay triangulation highly inefficient

Sylvain Pion
Administrator
Le 05/08/10 10:00, Ben Haller a écrit :
>    I would like to know when this new algorithm makes it into the official CGAL distribution, though.  Will that be announced on this list, or do I need to subscribe to something else?

Release announcements are made here, as well as on cgal-announce,
and also on some other non-cgal lists.

--
Sylvain

--
You are currently subscribed to cgal-discuss.
To unsubscribe or access the archives, go to
https://lists-sop.inria.fr/wws/info/cgal-discuss