Find all intervals that are contained in a query interval

Question

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?

Answer 1

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.

Answer 2

This is an old question, but for the sake of posterity, there is a formulation that beats the worst-case $O(n)$ solution proposed by @D.W. with $O(\log n + k)$, where $k$ is the number of returned intervals. The trick is to think of each input interval $[i, j]$ as point $(i, j)$ on the 2-D plane. If you have a query interval $[x, y]$, containment is equivalent to $i \geq x$ and $j \leq y$. Thus, this formulation reduces the interval containment query to an orthogonal range query on points, with the query ranges being $[x, \infty) \times (-\infty, y]$. Listing the points can be solved in $O(\log n + k)$ time with $O(n)$ space by priority search trees (because the orthogonal ranges are infinite). You can also count the points in $O(\log n)$ time and $O(n \log n)$ space using a layered range tree (with fractional cascading, or $O(\log^2 n)$ time without it).