CGAL users discussion list

[Panagiotis Foteinos <>]

There is only one infinite vertex which adds nothing to space complexity. 
I think that the number of infinite cells is what you should be worried about. If you have many of your input points lying exactly on the convex hull then you expect a large number of infinite cells. The infinite cells are useful, but they consume memory and have no physical meaning.

I am not sure I understand your "scalability" question well: 

just to load 176M (float) points into the memory, you need more than 1.9G memory space, not taking into account the memory the data structures themselves need, which is a lot... So, the only solution is disk, which has never been scalable...

On Thu, Jan 7, 2010 at 12:17 PM, Tauheed Farhan <> wrote:

________________________________________
From: Sylvain Pion []
Sent: 07 January 2010 17:52
To:
Subject: Re: [cgal-discuss] Scalable Delaunay Triangulation 3D

Tauheed Farhan wrote:
>   I have a problem I have 173 million data points and I want to do 3d delaunay triangulation

Interesting.

>   I run out of memory after doing 6million because the incremental algorithm adds "auxiliary" vertices which i dont use.

I'm puzzled by your sentence.  Which vertices don't you use ?
The only vertices added by the Delaunay triangulation are the points that
you pass to it.  Are there some of them that you would like to get rid of
to avoid building the full Delaunay triangulation ?

I meant the algorithm adds additional vertices while computing the delaunay triangulation . they call them infinite vertices which are far more than the actual vertices,
http://www.cgal.org/Manual/3.2/doc_html/cgal_manual/TriangulationDS_3/Chapter_main.html
I dont care about these infinite vertices which the algorithm adds, my concern is only with the actual vertices I gave as input.
The algorithm fills up my 2GB memory after inserting 6 million points. I'm using triangulation_hierarchy_3 class which builds the delaunay incrementaly
I have a 32bit windows machine and cannot access more than 2GB of main memory per application

>   Can any one help me out to implement a disk based "external memory" implementation?

I never went as far as 173M.  I think the largest I tried was 50M (random) points,
it went smoothly on a 16GB machine, using normal swap and doing nothing special
(due to the local swap-friendly order which is used).
This technique is simplistic, but might work.

I have not seen more involved schemes implemented with CGAL so far, although
there is related out-of-core non-CGAL work (e.g. by Martin Isenburg et al).

I'm interesting in helping on this.

I'm checking Martin Isenburg work on streaming delaunay thanks a lot for the link
If i understood you correctly you are suggesting I do the delaunay triangulation on partitions of data that can fit in memory and swap the result of delaunay
in and out of memory. how would I stitch the results of delaunay triangulation of different partitions together if I follow this path?.
 I'm not sure if i fully understood when u mentioned the local swap friendly order

many thanks again mate
Farhan



--

Sylvain Pion
INRIA Sophia-Antipolis
Geometrica Project-Team
CGAL, http://cgal.org/

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


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