2
$\begingroup$

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?

$\endgroup$
0

1 Answer 1

0
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$
    – jsguy
    Dec 7, 2014 at 19:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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