2.1. Interval Trees

The interval tree is used for answering the following one-dimensional (interval/point) stabbing query efficiently :

Input: a set S of closed intervals on the line;
Query: a single value x _q ˆˆ ;
Output: all intervals I ˆˆ S with x _q ˆˆ I .

For example, in Figure 2.1, there are seven intervals s ₁ , s ₂ , , s ₇ and a query value x _q . For convenience, the intervals are illustrated by horizontal line segments s _i in 2D and the query value is illustrated as a horizontal line x _q . The (interval/point) stabbing query should report the segments s ₂ , s ₅ , and s ₆ . We can assume that a segment s _i is represented by the x -coordinate of its left and right endpoints l _i and r _i , respectively.

Figure 2.1: An example of the node information in an interval tree. For convenience, the intervals are represented by 2D line segments. The left and right endpoints l _i and r _i of the segments s _i hit by the median x _med are represented in sorted lists M _L and M _R , respectively.

We construct a data structure that answers the above query efficiently. The information of the intervals are stored in a binary tree. Let S denote a set of n intervals [ l _i , r _i ] for i = 1 , , n . The binary interval tree is constructed recursively, as shown in the construction sketch. A node of the tree is dedicated to a median value of the endpoint of all segments. For all segments that contain this value, there are two lists for checking wether a query value is also covered by those intervals; see Figure 2.1 for an example of the node information. The query operation will be explained in detail later in this chapter.

The following is the interval tree construction algorithm sketch (see also Algorithm 2.1):

Input: given a set of intervals S represented by [ l _i , r _i ] for i = 1 , , n ;
If S is empty, then the interval tree is an empty leaf. Otherwise, allocate a node v with two children;
For the node v , compute the median x _med of { l ₁ , , l _n , r ₁ , , r _n }. This means that half of the interval endpoints lie to the left and half of the interval endpoints lie to the right of x _med . Note that the median normally will not be equal to a value l _i or r _i ;

Let L _med denote the set of intervals to the left of x _med , let S _med denote the set of intervals that contain x _med , and let R _med denote the set of intervals to the right of x _med ;

Algorithm 2.1: Computing an interval tree for a set of intervals, recursively.

IntervalTree( S ) ( S is a set of intervals {[ l ₁ ,r ₁ ] , , [ l _n ,r _n ]} together with sorted lists for { l _i }, { r _i }, and { l _i } ˆ { r _i })

  if   S  =     then   return  Nil  else   v  := new node  v.S  _med := HitSegments(  v.x  _med  ,S  )  v.x  _med := Median(  S  )  R  _med := RightSegments(  v.x  _med  ,S  )  L  _med := LeftSegments(  v.x  _med  ,S  )  v.M  _L := SortLeftEndPoints(  v.S  _med )  v.M  _R := SortRightEndPoints(  v.S  _med )  v.  LeftChild := IntervalTree(  L  _med )  v.  RightChild := IntervalTree(  R  _med )  return   v   end if

At the root v , store x _med and build a sorted list M _L for all left endpoints of S _med and a sorted list M _R for all right endpoints of S _med ;
Build the interval trees for L _med and R _med recursively for the children of v .

Algorithm 2.1 computes the interval tree efficiently, as shown in Lemma 2.1.

Lemma 2.1. The interval tree for a set S of n intervals has size O ( n ) and can be constructed in O ( n log n ) time.

Proof: In a preliminary step, we sort the interval endpoints by l _i order, by r _i order, and by total ( l _i and r _i ) order. Obviously, the depth of the constructed tree is in O (log n ). Let n _v denote the number of intervals at node v . Computing the median takes O ( n _v ) time using the total order of the interval endpoints. Let m _v = S _med for the set of intervals S _med at v . Computing M _L and M _R from the l _i and r _i order takes at most O ( m _v ) time. Since all occurring sets S _med are distinct, this gives O ( n ) altogether. Maintaining the l _i , r _i , and total order for the recursive steps takes O ( n _v ) time. Altogether, with the recursive steps, we have the recursive cost function . Together with the depth O (log n ) of the tree, we conclude the given result.

Next, we consider the recursive stabbing query operation for a value x _q ˆˆ and the root v of the interval tree. The median x _med of node v is used for binary branching. The node information is used for answering the stabbing query for the intervals that contain the median.

Algorithm 2.2: Answering a stabbing query for an interval tree v and a value x _q , recursively.

IntervalStabbing( v, x _q ) ( v is the root of an interval tree, x _q ˆˆ )

  D  := new list  if   v.x  _med  < x  _q  then   L  :=  v.M  _L  f  :=  L.  First  while   f    Nil and  f < x  _q  do   D.  ListInsert(Seg(  f  ))  f  :=  L.  Next  end while   D  ₁ := IntervalStabbing(  v.  LeftChild  , x  _q )  else if   v.x  _med    x  _q  then   R  :=  M  _R (  v  )  l  :=  R.  Last  while   l    Nil and  l > x  _q  do   D.  ListInsert(Seg(  l  ))  l  :=  R.  Prev  end while   D  ₁ := IntervalStabbing(  v.  RightChild  , x  _q )  end if   D  :=  D.  ListAdd(  D  ₁ )  return   D

The following is the stabbing query operation sketch:

Input: given the root v of an interval tree and the query point x _q ˆˆ ;
If x _q < x _med then
- Scan the sorted list M _L of the left endpoints in increasing order and report all stabbed segments. Stop if x _q is smaller than the current left endpoint;
- Recursively, continue with the interval tree of L _med ;

If x _q > x _med then
- Scan the sorted list M _R of the right endpoints in decreasing order and report all stabbed segments. Stop if x _q is bigger than the current right endpoint;
- Recursively, continue with the interval tree of R _med .

For example, assume that there is a stabbing query at a node v as pointed out in Figure 2.1. Starting from the left with M _L , the segments s ₅ and s ₆ are reported since x _q lies to the right of l ₅ and l ₆ . Then the stabbing query recursively goes on with L _med and will find s ₂ .

Lemma 2.2. An (interval/point) stabbing query with an interval tree for a set S of n intervals and a value x _q ˆˆ report all k intervals I of S with x _q ˆˆ I in O ( k + log n ) time.

Proof: Scanning through M _R or M _L at node v takes time proportional to the number of reported stabbed intervals because we stop as soon as we find an interval that does not contain the point x _q . The sets S _med of all v are distinct, which gives O ( k ) for all scannings. The size of the considered subtree is divided by at least two at every level, which gives O (log n ) for the path length. Altogether, the given bound holds.

The interval tree was considered in [Edelsbrunner 80] and [McCreight 80]. Note that the interval tree has no direct generalization to higher dimensions, but can support combined queries; see Section 2.6.

A WeakDelete operation for a segment s (see Chapter 10) can be done in O (log n ) time. We find the corresponding node with s ˆˆ S _med and mark the endpoints as deleted in the sorted lists M _L and M _R .

Lemma 2.3. A WeakDelete operation for a segment s in an interval tree of n intervals is performed in O (log n ) time.