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
> > 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),
> > the aim here is to adapt a 1D data structure. I have used the Z-curve
> > method  to do this efficiently for some years now and it works well.
> > 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,
> Interval Container Library [Boost.Icl]
That is an interesting idea. However, I see the method (or at least some
of it) are covered by a patent. Presumably that could affect its adoption into
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
adapters fitting over sets or maps so this would be a good fit. It might thus
be quicker to integrate.