efficient interval containment lookup

[Gabriel Genellina]

En Tue, 13 Jan 2009 02:55:36 -0200, Per Freem <perfreem at yahoo.com>  
escribió:

> On Jan 12, 10:58 pm, Steven D'Aprano
> <ste... at REMOVE.THIS.cybersource.com.au> wrote:
>> On Mon, 12 Jan 2009 14:49:43 -0800, Per Freem wrote:
>> > thanks for your replies -- a few clarifications and questions. the
>> > is_within operation is containment, i.e. (a,b) is within (c,d) iff a
>> >>= c and b <= d. Note that I am not looking for intervals that
>> > overlap... this is why interval trees seem to me to not be relevant,

> i found an implementation (which is exactly how i'd write it based on
> the description) here:  
> http://hackmap.blogspot.com/2008/11/python-interval-tree.html
>
> when i use this however, it comes out either significantly slower or
> equal to a naive search. my naive search just iterates through a
> smallish list of intervals and for each one says whether they overlap
> with each of a large set of intervals.

I think there is an algorithm by Baeza-Yates that handles efficiently what  
you want; but I can't find it. Perhaps Google works better for you. It  
might be only available in Spanish, though.

-- 
Gabriel Genellina