Re: [Caml-list] Fwd: interval trees

[Francois Berenger <berenger@riken.jp>]

On 02/16/2012 12:21 AM, Goswin von Brederlow wrote:
> Francois Berenger<berenger@riken.jp>  writes:
>
>> Hello,
>>
>> I did a naive implementation of interval trees for float intervals.
>>
>> It is available here:
>> https://github.com/HappyCrow/interval-tree
>>
>> I wonder if it is possible to construct the trees in a tail recursive
>> fashion. Maybe I knew how to do this when I was still at university.
>>
>> Regards,
>> Francois.
>
> | Node of
>     (* x_mid left_list right_list left_tree right_tree *)
>        float * interval list * interval list * interval_tree * interval_tree
>
> Why interval list? You only need a single interval in leafes and none in
> other nodes (although it can help to store min and max in each node).

Not in my case, there is a payload associated with each interval in my 
application so I need to keep track of the individual intervals.

> You are also missing insert and remove operations,

I don't miss anything: I don't need these operations in my application.

 > which is the actually
> hard part in this. Inserting an interval might require merging the
> rightmost interval left of the root and the leftmost interval right of
> the root. So you would have 2 removals and one insertion of a combined
> interval, which complicates balancing the whole thing efficiently.

I hope you have a good book on this.
By the way, the one I refer to in my code is quite nice.
At first I thought it was too theoretical for me, but in fact
they give algorithms in recursive form so the book can become pretty handy.

> That is the part I'm struggling with.

You might be intersted into having a look at
the Computational Geometry Algorithms Library: http://www.cgal.org/
It's open source and it's also an INRIA product,
which makes two good points. ;)

You might want to bind your code to this library (they introduced
some framework recently, SWIG if I remember well, so that it should be 
easy to do wrappers for any language).
It's heavily templated C++ code, good luck if you read their code.

They have a lot of crazily useful data structures (interval skip lists, 
k-d trees, segment trees, range trees, AABB trees), and their
code is impossible to crash when using some specific math kernels.

Regards,
F.