# 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. Dec 14, 2013 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, 2013 at 14:55
• Nope. Unless you're explicitly dealing with random input data, there is no such thing as "more likely". Dec 14, 2013 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, 2013 at 2:10

## 1 Answer

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.

• Thanks for that! I had never heard about it. Will look into it and mark your response as the answer.
– jbx
Dec 15, 2013 at 2:12
• Its actually quite close to what I managed to come up with, at least I wasn't far off. The part where you detect the ones that overlap completely the required interval was the missing one. Thanks for the link.
– jbx
Dec 15, 2013 at 21:21