Re: [boost] new library (space partitioning)

Subject: Re: [boost] new library (space partitioning)
From: Christoph Heindl (christoph.heindl_at_[hidden])
Date: 2010-07-28 05:20:21

Adam,

> I've implemented:
> - k-dimensional generalizations of STL containers (used by some space
> partitioning data structures)
> - k-dimensional space partitioning data structures
>        - regular grid
>        - kd-tree
>        - something I've called regular tree,
>        it's k-dimensional generalization of quadtree/octree,
>        so for k=2 it's quadtree, for k=3 it's octree,
>        for k=4 it's 16tree and so on.
> - k-dimensional euclidean algebra/geometry data structures
>        - points, vectors etc.,
> - unit tests.
>
> There are boost-like names used in code allready. If you'd like to know more
> just ask.

I'm interested too.

I might be able to contribute as I'm using space partitioning
structures on an every day basis.

Here are a couple of questions
 - what kind of split policies are implemented for the k-d tree?
 - how do you cope with unbalanced trees caused by  dynamic
insertion/deletion of points?
 - what queries are supported (i.e nearest neighbors, arbitrary
volumes, parametric volumes) ?
 - do you offer incremental queries that can be stopped before
evaluating the entire result set ?
 - did you consider to implement parallel queries ?
 - where's the code?

Best regards,
Christoph