# Find all intervals that are contained in a query interval

Given a set of intervals $S = I_1, ..., I_n$, what is the fastest way to find all intervals of $S$ that are completely contained in an interval $I_\text{query}$? It should also support incremental (dynamic) insertion of new intervals to $S$.

Interval trees are not suitable for this, since they are designed to query overlapping intervals. Similarly, segment trees are designed to query all intervals that contain a query point.

A solution would be to use an interval tree to find overlapping intervals, then use linear search and eliminate those from the results that are outside of the specified query interval.

Is there any better/faster solution for this?

You were too quick to reject interval trees and segment trees. You can search an segment tree for all intervals that are contained in a query interval $q=[\ell_q,u_q]$, using a straightforward recursive procedure:

Any node $v$ of a segment tree has a corresponding interval $\text{Int}(v)$. Do a recursive search of the tree, except that you only visit nodes $v$ such that $\text{Int}(v)$ overlaps $q$. Each such node stores a list of intervals from $S$. For each such node, if $\text{Int}(v)$ is contained in $q$, check all of the intervals stored with $v$ is contained in $q$.

That's all you need to do. Just because a data structure is designed to support one kind of operation doesn't mean it's unable to support other operations, too.

That said, one challenge with segment trees is that it's not clear how to update them dynamically (to add new intervals).

I think similar ideas can also be applied to interval trees, too. The root of an interval tree has a value $x$. Now do a case analysis:

• If $x$ is to the left of $q$ (i.e., $x < \ell_q$), then you only need to look at intervals that are completely to the right of $x$, so you just recurse to the right child of the root.

• If $x$ is to the right of $q$ (i.e., $x > u_q$), then you only need to look at intervals that are completely to the left of $x$, so you just recurse to the left child of the root.

• If $x \in q$ (i.e., $\ell_q \le x \le u_q$), then you recurse to the left child and output all matches found there; recurse to the right child and output all matches found there; and finally, find all intervals that contain $x$ and are contained in $q$. The latter can be done by scanning the list of intervals associated with the root (which is a list of intervals that contain $x$), to see which meet your condition.

I suspect there might be other approaches as well. For instance, you could build a $k$-d tree, with $k=2$ dimensions, where the interval $[\ell,u]$ is represented as the point $(\ell,u)$. Then given a query interval $q=[\ell_q,u_q]$, you want to do a range search to find all points $(x,y)$ such that $x \ge \ell_q$ and $y \le u_q$. That should be a straightforward recursive search in a $k$-d tree. Or, you could build a quadtree.

• The problem with the segment tree approach is that since the segment tree stores most intervals on multiple nodes, the query list will contain duplicates, which must be removed, or rejected. – plasmacel Jun 20 '17 at 18:25
• @plasmacel, OK. One can eliminate duplicates pretty easily (e.g., with a hashtable). – D.W. Jun 20 '17 at 20:20