# Fast extraction of pairs overlapping an interval

I am trying to find a fast algorithm to extract pairs that overlap with a specified interval.

Lets say I have a long list of pairs of integers, each pair (x1, x2) assuming x1 <= x2, (you can imagine them two points on the x-axis or on a timeline to visualise the problem better). Provided 2 other values V1, and V2, also assuming V1 <= V2, I want to extract the set of all pairs that satisfy at least one of the following criteria.

1. V1 <= x1 <= V2
2. V1 <= x2 <= V2
3. x1 <= V1 <= V2 <= x2

So intuitively what I need to extract is all interval pairs that overlap with V1 and V2, either partially (criteria 1 and 2) or completely (criteria 3).

I wish to find a fast way to extract them (I know this depends on how large the interval between V1 and V2 is). The solution I came up with so far is organising the pairs in a balanced binary search tree sorted with just x1 and traversing it for items that are x1 <= V2, and then checking the rest of the criteria as I am traversing the tree. I could also enhance it by adding another binary search tree sorted by x2 of the same pairs, and traversing similarly for pairs x2 >= V1, and maybe using this tree instead when the V1, V2 interval is biased towards the right of the midpoint of the whole range of values of the pairs.

Is there any better idea how I could achieve this? It seems I can only get O(n) complexity.

• I know this depends on how large the interval between V1 and V2 is — No, it doesn't. – Jeffε Dec 14 '13 at 14:31
• I think it does, because the larger the interval its more likely you have to check 'deeper' before you can exclude the rest, depending on how the pairs are organised I guess, but I am open to ideas, which is why I am asking – jbx Dec 14 '13 at 14:55
• Nope. Unless you're explicitly dealing with random input data, there is no such thing as "more likely". – Jeffε Dec 14 '13 at 18:37
• Its not random, but I can't predict how it will be. The user of the system will input these pairs, so I can only think what the likely distribution is going to be, given the application. – jbx Dec 15 '13 at 2:10

This is a standard geometric data structure problem, which can be solved by storing the intervals $(x_1, y_1), \dots, (x_n, y_n)$ in an interval tree. Then you can extract all the intervals $(x_i,y_i)$ overlapping a given query interval $(X,Y)$ in $O(\log n + k)$ time, where $k$ is the number of output intervals.