1
$\begingroup$

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?

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – plasmacel Jun 20 '17 at 18:25
  • $\begingroup$ @plasmacel, OK. One can eliminate duplicates pretty easily (e.g., with a hashtable). $\endgroup$ – D.W. Jun 20 '17 at 20:20
  • $\begingroup$ These approaches (except for the last, k-d tree one) have a very bad time complexity, ultimately equal to brute forcing, i.e. O(n). To make this obvious, on the Interval Tree approach, you recurse on the third case both on the left and right subtrees, therefore visit O(n) nodes in the worst case. This is in contrary to the overlapping search algorithm for an Interval Search, which when interested only for the existence of an overlapping interval, also according to CLRS book, is O(logn). Is there any O(logn) algorithm for this problem on an Interval Tree? $\endgroup$ – Jason Aug 13 at 0:35
  • $\begingroup$ @Jason, I don't know. Good question! I suggest asking a separate question about that. I do suggest using output-sensitive analysis to think about this situation. Any algorithm will have worst-case running time $O(n)$, as in the worst case the response to the query might need to include all intervals; but it's better to measure the running time as a function of $k$, the number of intervals in the response, and $n$, the total number of intervals. If we're lucky, we could hope for a running time of $O(k + \log n)$. I don't know whether that is attainable for interval trees or not. $\endgroup$ – D.W. Aug 13 at 1:34
  • $\begingroup$ @D.W. this question has many similarities on the discussed matter, mind the low views and zero responses, as of now: cs.stackexchange.com/questions/112658/… $\endgroup$ – Jason Aug 13 at 16:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.