Practical Applications of Interval Tree

Question

I have googled about this topic a bit and found this on http://www.geeksforgeeks.org/

Interval tree is mainly a geometric data structure and often used for windowing queries, for instance, to find all roads on a computerized map inside a rectangular viewport, or to find all visible elements inside a three-dimensional scene.

Now my question is actually in two parts:

• How is interval tree used to find all roads on a computerized map?
• What are some other example of practical applications of interval tree?

P.S: Brief explanations with reference to more reading materials on interval tree will be more than welcomed

Answer 1

Maybe not directly answer your question but I think it might helpful:

Enclosing Interval Searching Problem: Given a set S of n intervals and a query point, q, report all those intervals containing q.

Overlapping Interval Searching Problem: Given a set S of n intervals and a query interval Q, report all those intervals in S overlapping Q.

Reference (also compare with other similar data structure like segement tree): http://www.iis.sinica.edu.tw/~dtlee/dtlee/CRCbook_chapter18.pdf

Answer 2

In the windowing query, given a set of line segments and an axis-aligned rectangle, we have to find the intersections of the line segments with the rectangle. This can be solved by using Interval Trees in combination with Range Trees.

Range Trees are an efficient data structure for finding the set of points present within a Range/Rectangle. So they can be used to find all the line segments such that one of the end points of each line segment is present in the query Rectangle. These correspond to the blue line segments in the figure below.

Interval Trees can be used to find those segments that overlap with the window but whose endpoints are outside the window. These are the red segments in the figure.

Before solving this problem, imagine a more restricted version of the problem in which all line segments are horizontal or vertical. In this case any horizontal segment that intersects the rectangle should intersect the left (and right) vertical edge of the rectangle. If we think of the horizontal segments as intervals and the vertical edge of the rectangle as a point, the problem is to find all the intervals that contain the point. Thus we can solve this problem using interval trees. Similarly we can find all intersecting vertical line segments.

The general version of the problem where line segments aren't parallel to axis cannot be solved perfectly using interval trees. However we can use interval trees to eliminate the overwhelming majority of the line segments that don't overlap with the query rectangle. For each line segment in the input, we construct an axis-parallel rectangle whose diagonal is the line segment. We then construct (horizontal and vertical) interval trees using the sides of the rectangles. Given a query rectangle R, we can first find all rectangles that intersect R as before. The corresponding line segments have a high chance of intersecting with R and can be checked individually for actual intersection.