CGAL users discussion list

[Tao Go <>]

Hi Fabri,
    Many thanks for the reply.

Lincong

--- On Mon, 10/5/09, Andreas Fabri <> wrote:

From: Andreas Fabri <>
Subject: Re: [cgal-discuss] Space complexity of the CGAL range search tree: needs large amount of memory
To:
Date: Monday, October 5, 2009, 7:18 AM

Hello Lincong,

the problem is that the implementation is very generous in memory usage
and would profit from some optimization.

But even with that optimization its complexity is O( n log^d( n ) )
which sounds fine in theory, but the log n to the power of d is a
rather big multiplicative constant in practice.

best regards,

andreas


Tao Go wrote:
> Dear All,
>    I tried to use the CGAL range search tree as follows. What surprised me is that the more than 2G memory is needed to create a range-search tree with about 36,000 3D integer points. I posed  the part of code involving CGAL functions here. Anyway help for reducing the memory requirement is very appreciated.  In other words, do I use these CGAL functions in a wrong way?
> Many thanks!
> Best,
> Lincong
> __________________________________________________
>
> #include <CGAL/basic.h>
> #include <CGAL/Cartesian.h>
> #include <CGAL/Range_segment_tree_traits.h>
> #include <CGAL/Range_tree_k.h>
>
> typedef CGAL::Cartesian<int>  K;
> typedef CGAL::Range_tree_map_traits_3<K, int> Traits;
> typedef Traits::Key Key;
> typedef Traits::Pure_key Pure_key;
> typedef Traits::Interval Interval;
> typedef CGAL::Range_tree_3<Traits> Range_tree_3_type;
>
> // The code using CGAL
>
> const size_t noOfCube = emptyCube.size();  // the size is 63701 for the example
>  // where  the variable "emptyCube" is a "vector<pair<size_t, float> >"
>     std::list<Key> InputList;
>     std::list<Key> OutputList;
>     std::list<Key>::iterator first, last, current;
>     int index, indexX, indexY, indexZ;
>     current = InputList.begin();
>       for (unsigned int i = 0; i < noOfCube; i++, current++){
>         index = emptyCube[i].first;
>         indexX = index % noOfStep;  // noOfStep == 81
>         indexY = ( ( index - indexX ) / noOfStep ) % noOfStep;
>         indexZ = ( ( index - indexX ) / noOfStep - indexY ) / noOfStep;
>         InputList.push_back( Key( K::Point_3( indexX, indexY, indexZ ), ( i + 1 ) ) ) ;
>     }
>
>      first = InputList.begin();
>     last = InputList.end();
>     Range_tree_3_type Range_tree_3(first, last);
>
>
>

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