<p>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 <a href="https://en.wikipedia.org/wiki/Interval_tree">interval tree</a>.  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.</p>

CC BY-SA 3.0
2013-12-15T02:12:15.377Z
Thanks for that! I had never heard about it. Will look into it and mark your response as the answer.
jbx
CC BY-SA 3.0
2013-12-15T21:21:14.493Z
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
CC BY-SA 3.0
2013-12-14T18:45:51.570Z
2013-12-14T18:45:51.570Z
Jeffε
<p>I am trying to find a fast algorithm to extract pairs that overlap with a specified interval.</p>

<p>Lets say I have a long list of pairs of integers, each pair (x1, x2) assuming x1 &lt;= 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 &lt;= V2, I want to extract the set of all pairs that satisfy at least <strong>one</strong> of the following criteria.</p>

<ol>
<li>V1 &lt;= x1 &lt;= V2</li>
<li>V1 &lt;= x2 &lt;= V2</li>
<li>x1 &lt;= V1 &lt;= V2 &lt;= x2</li>
</ol>

<p>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).</p>

<p>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 &lt;= 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.</p>

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

CC BY-SA 3.0
2013-12-14T14:31:47.017Z
_I know this depends on how large the interval between V1 and V2 is_ — No, it doesn't.
Jeffε
CC BY-SA 3.0
2013-12-14T14:55:17.383Z
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
CC BY-SA 3.0
2013-12-14T18:37:41.320Z
Nope.  Unless you're explicitly dealing with random input data, there is no such thing as "more likely".
Jeffε
CC BY-SA 3.0
2013-12-15T02:10:42.027Z
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
<sorting>
Fast extraction of pairs overlapping an interval
jbx
# Fast extraction of pairs overlapping an interval

(Asked by: username_0 on 2013-12-14)

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.

**Tags:** sorting

> **Comments:**
> **username_1**: _I know this depends on how large the interval between V1 and V2 is_ — No, it doesn't.  
> **username_0**: 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  
> **username_1**: Nope.  Unless you're explicitly dealing with random input data, there is no such thing as "more likely".  
> **username_0**: 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.  

---

## 1 answers

### Answer by username_1 on 2013-12-14. Score: 6 | Accepted 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](https://en.wikipedia.org/wiki/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.

> **Comments:**
> **username_0**: Thanks for that! I had never heard about it. Will look into it and mark your response as the answer.  
> **username_0**: 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.  

---

