7
$\begingroup$

Note: I moved this question from stackoverflow.com

I have an algorithmic problem where I would like to see if it can be solved in better than $O(n)$:

I have given a table $T$ of $n$ elements where each element is a tuple $(s_i, e_i)$ with $s_i, e_i \in \mathbb{N}$ and $s_i < e_i$, i.e. each tuple is some kind of an interval. I have to find all intervals that overlap with a given interval $[t_0, t_1]$ with $t_0, t_1 \in \mathbb{N}$ and $t_0 < t_1$. Further, I have available two sorted lists $S$ and $E$, containing the $s$ values, or $e$ values respectively, together with the index $i$ pointing to the respective entry in $T$. The lists are sorted by $s$ values, or $e$ values respectively. (Let's assume both, $s$ and $e$ values, are unique.)

Problem:

We have to find each interval/tuple $(s_i, e_i) \in T$ where $s_i \leqslant t_1$ and $e_i \geqslant t_0$.

My thoughts so far:

We can exclude some elements by either applying one of the interval boundaries, i.e. searching $t_1$ in $S$ or $t_0$ in $E$. This gives us a list $L$ of remaining elements: $$ L \leftarrow \{e \in E \mid e \geqslant t_0\} \text{ or } L \leftarrow \{s \in S \mid s \leqslant t_1\} $$ However, there is no lower bound on the number of elements in $L$, no matter which search we perform. Further, we have to check every element in $L$ if $s \leqslant t_1$, or $e \geqslant t_0$ respectively depending on which search we performed before.

The complexity for this solution is $O(n)$.

However, let's say that $k$ is the maximum number of elements overlapping with interval $[t_0, t_1]$. If we assume $k \ll n$, then the complexity is $O(n/2)$ since we can exclude at least $n/2$ elements by choosing the appropriate search for $L$. Still $O(n/2)$ is in $O(n)$.

Can you think of a better approach to solve this problem?

For record:

The complexity for finding all intervals overlapping with a certain given interval using an interval tree is $O(\log n + k)$ where $k$ is the number of overlapping intervals. However, in my practical case I am using a MySQL database which provides index trees for each value, i.e. $s$ and $e$, separately. This way I can not find overlapping intervals in less than $O(n)$. I would need to create an interval tree which is a search tree that stores both interval boundaries, i.e. $s$ and $e$, in a single data structure. The complexity for constructing the interval tree is $O(n \log n)$. [http://www.dgp.utoronto.ca/people/JamesStewart/378notes/22intervals/]

$\endgroup$
  • 2
    $\begingroup$ If $k \ll n$, I think there is a pre-computation of $O(nk)$ space, resulting in $O(k^2+\log n)$ time lookups. I wonder if that's okay. $\endgroup$ – Karolis Juodelė Sep 14 '13 at 20:41
6
$\begingroup$

I believe that interval trees offer a solution to your problem. Basically, you store your intervals in the interval tree data structure; then, to find all intervals that overlap with $[t_0,t_1]$, you do a query into the interval tree. This should solve your problem and run faster than $O(n)$ time.

$\endgroup$
  • $\begingroup$ Thanks for the reference. However, for the initial problem, I think there is no better solution than $O(n)$. Only if I can assume that $k \ll n$, we can be faster however, unfortunately, this assumption does not really hold in my case. Thanks. $\endgroup$ – sema Sep 15 '13 at 20:29
  • 1
    $\begingroup$ @sema, I'm confused. If there are $k=\Theta(n)$ overlapping intervals, then of course you can't do better than $O(n)$ time, and in that case you might as well just check each of the intervals in the set -- so I'm not sure what your question is, or why you are asking (you already have a proof that one cannot do better than the naive algorithm). In contrast, if $k=o(n)$, interval trees do better than just checking each possible interval. In general, the running time of interval trees is based upon the number of matches, so their running time is close to the best one could hope for. $\endgroup$ – D.W. Sep 15 '13 at 21:44
  • $\begingroup$ Sorry for confusion. I just agree with you and summarized for myself, that it would be desirable to find a upper bound on $k$ such that $k \ll n$. With the general problem, we are stuck with $O(n)$ where we can't do better. Thanks for your answer and the reference to interval trees. $\endgroup$ – sema Sep 16 '13 at 3:30
  • $\begingroup$ You should probably include the time spent on creating the interval tree in your answer. $\endgroup$ – Raphael Sep 16 '13 at 8:04
  • $\begingroup$ @sema The notation $k \ll n$ does not make much sense in asymptotic terms. You want to use $k \in o(n)$. $\endgroup$ – Raphael Sep 16 '13 at 8:04

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.