Re: [boost] Interval Trees & ICL

Subject: Re: [boost] Interval Trees & ICL
From: Bruce Adams (tortoise_74_at_[hidden])
Date: 2010-12-17 12:39:02

----- Original Message ----

> From: Joachim Faulhaber <afojgo_at_[hidden]>
> To: boost_at_[hidden]
> Sent: Fri, December 17, 2010 12:32:48 AM
> Subject: Re: [boost] Interval Trees & ICL
> 
> 2010/12/16 Phil Endecott <spam_from_boost_dev_at_[hidden]>:
> >   My idea is to
> > consider an interval (low,high) as a point in a 2D  plain.  Then, a query to
> > find all of the intervals overlapping (a,b) is  the same as the query to 
find
> > all the points in the quarter-plane where  low<b and high>a.
> >
> > Any 2D data structure could be used to  store these (e.g. quadtrees etc), 
but
> > the aim here is to adapt a 1D data  structure.  I have used the Z-curve
> > method [3] to do this efficiently  for some years now and it works well. 
 The
> > idea is that you  bitwise-interleave the two values and use this as the key.
> >  You can then  iterate over all points in a rectangle by iterating over all
> > points in  the 1D range between the interleaved bottom left and top right
> > corner  values.
> 
> Hi Phil,
> 
> I find your idea quite nifty and fascinating. The  transformation from
> intervals to 2D plane to z-curve ordering is quite  powerful and opens
> up new frames of thinking on the problem. I guess I need a  little more
> thinking time and intend to post another answer  tomorrow.
> 
> Best regards,
> Joachim
> 
> -- 
> Interval Container  Library  [Boost.Icl]
> http://www.joachim-faulhaber.de

That is an interesting idea. However, I see the method (or at least some 
implementations
of it) are covered by a patent. Presumably that could affect its adoption into 
boost? 

I'm broadly against software patents but things get hairy if you give the 
lawyers a hook 

to fish with. Actually digging a bit further it could be that the patent is to 
prevent evil lawyers
doing this as the claim is by an academic rather than say Oracle (unless he 
works for Oracle!)
Looks like enough of it is prior art that something could be used.

I note that the current interval containers could also be considered / are 
implemented as
adapters fitting over sets or maps so this would be a good fit. It might thus 
be quicker to integrate.

Regards,

Bruce.