You want to create a data structure that can store 1 dimensional intervals and also support the query for finding the total amount of intervals intersecting a given point.

One solution would be for each query to scan through every interval and see if it is contained in this interval or not, this would give us O(amountOfQueries*n) time.

I'm not sure how you would achieve better bounds for these queries with interval trees. In these trees every node is an interval but it also contains the maximum end point of the set of all intervals in the right sub tree.

If for each query you decide to search for all intervals that contain it in this interval tree, then you can still get the O(n) time if all intervals contain this point.

So, how can interval trees help in this case?

up vote 0 down vote accepted

I think I have an algorithm but I'm not sure if it's correct.

We want to maintain an augmented binary search tree $S$ on each interval end point. The splitting element will always be the median end point so that the total height of our tree in the end is in the order of $\log_{2}N$.

In every node we use some data structure to store all intervals that go through the splitting element.

Assuming nothing more for our data structure, we can see that if $x_q$ is the query point, every time we visit a node we check to see if $x_{q}$ is to the right or to the left of the splitting element. If it is to the left, then no interval stored in any node of the right subtree will intersect $x_{q}$ so we will only need to check the left sub tree. The same applies to the case where $x_{q}$ is to the right of the splitting element.

So far we can find all relevant intervals in $O(\log n)$ time, but to find the exact intervals that intersect $x_{q}$, we have to see what's going on in this structure that we have for every node, so we also have to query each such structure along a root to leaf path to find exactly the intervals that intersect $x_{q}$

To do this, we can have two sorted lists $L$, $R$ on every node, each list will store the same intervals but $L$ will store them in a sorted order according to the left point and $R$ according to the right point.

Then whenever we visit a node we see if $x_{q}$ is to the left of the splitting element. If that's the case, we do a binary search on $L$ to find the right most interval that contains this point, since we know the index of this interval in $L$ we can find the total amount of intervals.

We process similarly $R$ if $x_{q}$ is to the right of the splitting element.

This algorithm will give us a $O(\log ^2 N)$ complexity.

  • the problem with this approach is that I'm not sure whether this is an actual interval tree or not. It's just a binary search tree where in each node we store some other binary search trees to support our operations. – jsguy Dec 7 '14 at 19:06

Your Answer

 
discard

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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