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);
- [cgal-discuss] Space complexity of the CGAL range search tree: needs large amount of memory, Tao Go, 10/04/2009
- Re: [cgal-discuss] Space complexity of the CGAL range search tree: needs large amount of memory, Andreas Fabri, 10/05/2009
Archive powered by MHonArc 2.6.16.