2.5. Range Trees

Range trees are defined for arbitrary dimension d and support exactly the same windowing query as the kd-tree. A range tree can answer the corresponding query more efficiently . On the negative side, a range tree requires more space than the kd-tree .

With the help of a d -dimensional range tree, one can efficiently answer (point/ axis-parallel box) windowing queries as follows :

Input: a set of points S in ;
Query: an axis-parallel d -dimensional box B ;
Output: all points p ˆˆ S with p ˆˆ B .

The range tree is defined similar to the multi-level segment tree (see Section 2.3). The main difference is that we do not need to represent segments in the tree. Let us first consider a simple balanced one-dimensional search tree for a set S of points on the x -axis. As mentioned earlier, each node v represents a uniquely determined interval v.I of points in S . In turn , for a query interval I , the points of S inside I are covered by a minimal set of intervals v.I ; see Figure 2.7. The construction of the one-dimensional search tree was already discussed in Section 2.2.

Figure 2.7: Every node v in the one-dimensional search tree represents a unique interval v.I. A query interval I is uniquely covered by a minimal set of intervals v.I.

For the inductive construction of a d -dimensional range tree, let x _i denote the i th coordinate. A point x _i ˆˆ S is given by ; see Figure 2.8 for a 2D example. A d -dimensional range tree with respect to ( X ₁ , X ₂ , , X _d ) is inductively defined as follows.

Figure 2.8: Some parts of the 2D range tree of eight points in 2D. The range tree T ¹ and the relevant trees

for the nodes u ₁ , u ₂ , and u ₃ with

, and

for the query rectangle R = I ₁ — I ₂ with intervals I ₁ X and I ₂ Y.

Algorithm 2.11: The inductive construction algorithm of a d-dimensional range tree.

RangeTreeConstr( D, d ) ( S is a set of points in )

  S  _f :=  S.  FirstCoordElements  S  _f  .  Sort  T  :=  S  _f  .  SearchTree  T.  Dim :=  d   if   d >  1  then   N  :=  T.  GetAllNodes  while   N        do   u  :=  N.  First  N.  DeleteFirst  L  :=  u.I   S  := new list  while   L        do   x  :=  L.  First  L.  DeleteFirst  S  :=  S.  ListAdd(  x.  Point(  d    1))  end while  Pointer(  u  ):= RangeTreeConstr(  S, d    1)  end while   end if   return   T

The following is the d -dimensional range tree construction sketch:

Build a one-dimensional balanced search tree T ¹ for all points x _i with respect to X ₁ ;
For every node u of T ₁ :
- Build a ( d ˆ 1)-dimensional range tree for the set of points
  
  where u.I represents the interval at node u in T ₁ ;
- Associate a pointer in T ¹ from u to .

The time and space complexity analysis for range a trees is very similar to the multi-level segment tree analysis; see the proof of Theorem 2.7. Since we do not have to insert segments into the trees, we can neglect a log factor.

The query operation for an axis-parallel query box q = I ₁ — I ₂ — — I _d and a d -dimensional range tree T ^d of a set of points p ₁ , , p _n T ^d is explained in the following sketch; see Figure 2.8 for an example.

The following is the range tree query sketch:

Algorithm 2.12: The inductive query operation for a d-dimensional range tree.

RangeTreeQuery( T, B, d ) ( T is the root of a d -dimensional range tree, B is a d -dimensional box)

  if   d  = 1  then   L  := SearchTreeQuery(  T, B  )  A  :=  L.  GetPoints  else   A  := new list  L  := MinimalCoveringIntervals(  T, B.  First)  while   L     do   t  := (  L.  First)  .  Pointer  D  := RangeTreeQuery(  t, B.  Rest  , d    1)  A.  ListAdd(  D  )  L.  DeleteFirst  end while   return   A   end if

If d = 1, answer the question with the corresponding one-dimensional search tree T ¹ ;
Otherwise, traverse T ¹ and find the nodes u ₁ , , u _l so that the intervals of the nodes ( u _i ) .I minimally cover I ₁ ;
For 1 ‰ i ‰ l , answer the query I ₂ — — I _d ⁽ ^d ^ˆ1) recursively with the trees of the data point sets of ( u _i ) .I .

Theorem 2.12. A d-dimensional range tree for a set of n points in dimension d can be built up in O ( n log ⁽ ^d ^ˆ ¹⁾ n ) time and needs O ( n log ⁽ ^d ^ˆ ¹⁾ n ) space. An axis-parallel box windowing query can be answered in O ( k + log ^d n ) time.

Proof: First, we sort the segments endpoints with respect to every dimension. The first range tree T ¹ is built up in O ( n ), has space O ( n log n ), and has O ( n ) nodes. Next, we construct ( d ˆ 1)-dimensional segment trees for the set of points in the interval v.I of every node v in T ¹ . Let v.I denote the number of data points in v.I . By induction, we can assume that the ( d ˆ 1)-dimensional segment tree for node v ˆˆ T ¹ with all points in v.I is computed in O ( v.I log ⁽ ^d ^ˆ ²⁾ v.I ). Additionally, every data point p occurs in O (log n ) intervals v.I ; i.e., in only O (log n ) ( d ˆ 1)-dimensional segment trees. Therefore, the overall running time is given by

The required space is measured as follows. The structure T ^d consists only of one-dimensional range trees T ¹ . In how many trees will a data point p _i appear? Since p lies inside O (log n ) intervals of T ¹ , the point p appears in O (log n ) trees . In each of these trees, the data point p again lies inside O (log n ) intervals and will be a data point in the corresponding trees. Altogether, a data point p appears in

nodes. Summing up over all n data points gives O ( n log ⁽ ^d ^ˆ ¹⁾ n ) entries. By the same argument, the number of trees is also in O (log ⁽ ^d ^ˆ ¹⁾ n ), so that the number of empty nodes is bounded by O ( n log ⁽ ^d ^ˆ ¹ ⁾ n ).

On the other hand, a query traverses along O (log ^d n ) nodes. For the first tree T ¹ , the query traverses O (log n ) nodes and O (log n ) new queries must be considered . Recursively, O (log n ) nodes of O (log n ) new trees may be traversed. In the final range trees, k boxes may also be reported . Altogether,

nodes are visited, and the running time for a query is O ( k + log ^d n ).

A WeakDelete operation (see Chapter 10) for a point p in the d -dimensional range tree can be performed in O (log ^d n ) time due to the number of nodes that must be traversed to find all entries belonging to p .

Lemma 2.13. A WeakDelete operation for a balanced d-dimensional range tree for n points in can be performed in O (log ^d n ) time.

Finally, with the help of the given results, we will answer a more general windowing query.