Re: [boost] Interval Trees & ICL

Subject: Re: [boost] Interval Trees & ICL
From: Joachim Faulhaber (afojgo_at_[hidden])
Date: 2010-12-17 16:31:27

2010/12/17 Bruce Adams <tortoise_74_at_[hidden]>:
> ----- 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.

After I have spent some more time studying your proposal, I still
think it is a very smart method and a good alternative to the
"classical" interval tree implementation suggested by Dave.

The restriction imposed by bit-interleaving on the applicable element
types is justified if the data structure gains efficiency. Using meta
programming we can choose the best implementation dependent on the
element type. More unpleasant is the fact that an important part of
the method, the efficient search of the z-ordered values within the
quarter-plane defined by the query interval seems to be protected by a
software patent as Bruce pointed out. But may be you have a different
implementation that circumvents this obstacle.

> 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

+1

Best regards,
Joachim

-- 
Interval Container Library [Boost.Icl]
http://www.joachim-faulhaber.de