Skip to Content.
Sympa Menu

cgal-discuss - Re: [cgal-discuss] Space complexity of the CGAL range search tree: needs large amount of memory

Subject: CGAL users discussion list

List archive

Re: [cgal-discuss] Space complexity of the CGAL range search tree: needs large amount of memory


Chronological Thread 
  • From: Andreas Fabri <>
  • To:
  • Subject: Re: [cgal-discuss] Space complexity of the CGAL range search tree: needs large amount of memory
  • Date: Mon, 05 Oct 2009 09:18:55 +0200


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);







Archive powered by MHonArc 2.6.16.

Top of Page