2.5. Range Trees

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 image from book ;

  • 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.

image from book
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 image from book ; see Figure 2.8 for a 2D example. A d -dimensional range tree with respect to ( X 1 , X 2 , , X d ) is inductively defined as follows.

image from book
Figure 2.8: Some parts of the 2D range tree of eight points in 2D. The range tree T 1 and the relevant trees image from book for the nodes u 1 , u 2 , and u 3 with image from book , image from book , and image from book for the query rectangle R = I 1 — I 2 with intervals I 1 X and I 2 Y.
Algorithm 2.11: The inductive construction algorithm of a d-dimensional range tree.
image from book

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

  S    f   :=  S.  FirstCoordElements  S    f    .  Sort  T  :=  S    f    .  SearchTree  T.  Dim :=  d   if   d >  1  then   N  :=  T.  GetAllNodes  while   N     image from book   do   u  :=  N.  First  N.  DeleteFirst  L  :=  u.I   S  := new list  while   L     image from book   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  
image from book
 

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

  • Build a one-dimensional balanced search tree T 1 for all points x i with respect to X 1 ;

  • For every node u of T 1 :

    • Build a ( d ˆ 1)-dimensional range tree image from book for the set of points

      image from book

      where u.I represents the interval at node u in T 1 ;

    • Associate a pointer in T 1 from u to image from book .

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 1 I 2 — — I d image from book and a d -dimensional range tree T d of a set of points p 1 , , 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.
image from book

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  
image from book
 
  • If d = 1, answer the question with the corresponding one-dimensional search tree T 1 ;

  • Otherwise, traverse T 1 and find the nodes u 1 , , u l so that the intervals of the nodes ( u i ) .I minimally cover I 1 ;

  • For 1 i l , answer the query I 2 — — I d image from book ( d ˆ1) recursively with the trees image from book 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 ˆ 1) n ) time and needs O ( n log ( d ˆ 1) 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 1 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 1 . 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 1 with all points in v.I is computed in O ( v.I log ( d ˆ 2) 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

image from book

The required space is measured as follows. The structure T d consists only of one-dimensional range trees T 1 . In how many trees will a data point p i appear? Since p lies inside O (log n ) intervals of T 1 , the point p appears in O (log n ) trees image from book . 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

image from book

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

On the other hand, a query traverses along O (log d n ) nodes. For the first tree T 1 , 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,

image from book

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 image from book 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.



Geometric Data Structures for Computer Graphics2006
Geometric Data Structures for Computer Graphics2006
ISBN: N/A
EAN: N/A
Year: 2005
Pages: 69

flylib.com © 2008-2017.
If you may any questions please contact us: flylib@qtcs.net