2.3. Multi-Level Segment Trees
 | ||
| | ||
| | ||
2.3. Multi-Level Segment Trees
In the preceding sections, we considered segment trees for 2D objects. Now, we generalize the approach. Namely, we consider the following multi-dimensional stabbing problem and make use of a set of inductively defined segment trees. Multi-level segment trees support ( axis-parallel box/point) stabbing queries as follows :
-
Input: a set S of n axis-parallel boxes in
; -
Query: a query point q in
; -
Output: all boxes B ˆˆ S with q ˆˆ B .
This stabbing query has many applications in computer graphics. For example, objects in the sphere may be approximated by their axis-parallel bounding box. For every point q , the (bounding box/point) stabbing query will report all objects that are near q . Figure 2.4 shows a simple example in 2D.
Figure 2.4: A stabbing query for a set of bounding boxes can report all polygonal objects near q.
A single d -dimensional box B i can be defined by a set of d axis-parallel segments 
starting at a unique corner 
; see Figure 2.5 for a 2D example. A multi-level segment tree T d with respect to ( x 1 , x 2 , , x d ), where x i denotes the i th coordinate, is inductively defined.
Figure 2.5: Some parts of the multi-level segment tree of four boxes in 2D. The segment tree T 1 and the relevant trees for the nodes u 1 and u 2 with
and 
for the query point q are shown. | |
MLSegmentTree( B, d ) ( B is a set of boxes in dimension d ; each box is represented by a set of line segments)
S := B. FirstSegmentsExtract T := SegmentTree( S ) T. Dim := d if d > 1 then N := T. GetAllNodes while Ndo u := N. First N. DeleteFirst L := u.L B := new list while L =
| |
The following is the multi-level segment tree construction sketch:
-
Build a one-dimensional segment tree T 1 for all segments
with respect to the x 1 coordinate; -
For every node u of T 1 :
-
Build a ( d ˆ 1)-dimensional multi-level segment tree
for the set of boxes 
where u.L denotes the set of segments stored at u in T 1 ;
-
Associate a pointer in T 1 from u to
.
-
A query is answered recursively in a straightforward manner. If a set of segments in dimension j has to be reported , we recursively check the corresponding tree with dimension j ˆ 1. The corresponding box is reported only if the query succeeds in every dimension. This means that finally we get an answer for a tree 
.
| |
MLSegmentTreeQuery( T, q, d ) ( q ˆˆ , T is the root node of a d -dimensional multi-level segment tree)
if d = 1 then L := StabbingQuery( T, q ) A := L. GetBoxes else A := new list L := SearchTreeQuery( T, q. First) while L do t := ( L. First) . Pointer B := MLSegmentTreeQuery( t, q. Rest , d 1) A. ListAdd( B ) L. DeleteFirst end while return A end if
| |
More precisely, a query for a query point q = ( q 1 , q 2 , , q d ) and a multi-level segment tree T d for a set of segments S 1 , , S n is given in the following sketch.
The following is the multi-level segment tree query sketch:
-
If d = 1, answer the question with the corresponding segment tree T 1 ; see Algorithm 2.6 and return the boxes associated to the segments reported;
-
Otherwise, traverse T 1 and find the nodes u 1 , , u l so that q 1 lies in the intervals ( u i ) .I of the nodes u i of T 1 for i = 1 to l ;
-
For 1 ‰ i ‰ l , answer recursively the query ( q 2 , , q d ) for the tree
of the set of segments ( u i ) .L stored at u i , respectively.
The following time and space bounds hold.
Theorem 2.7. A multi-level segment tree for a set of n axis-parallel boxes in dimension d can be built up in O ( n log d n ) time and needs O ( n log d n ) space. A (axis-parallel box/point) stabbing query can be answered in O ( k + log d n ) time.
Proof: First, we sort the segment endpoints with respect to every dimension. The first segment tree T 1 is built up in O ( n log n ) time, occupies space O ( n log n ), and has O ( n ) nodes. Next, we construct ( d ˆ 1)-dimensional segment trees for the set v.L of every node v in T 1 . By induction, we can assume that the ( d ˆ 1)-dimensional segment tree for a node v ˆˆ T 1 with v.L segments is computed in O ( v.L log ( d ˆ 1) v.L ). Additionally, as already proven, every segment s i occurs in O (log n ) lists v.L , i.e., in O (log n ) ( d ˆ 1)-dimensional segment trees. This means that 
is in O ( n log n ), and the overall running time is given by
The required space can be measured as follows. The whole structure T d consists of one-dimensional segment trees T 1 only. In how many trees will a part of the box B i appear? In the first tree T 1 , the segment 
of the box B i appears in O (log n ) nodes. Therefore, it appears in O (log n ) trees 
. In each of these trees, the segment 
of the box B i appears again in O (log n ) nodes. Altogether, segments of B i appear in
nodes. Summing up over all n segments gives O ( n log d n ) entries. By the same argument, the number of trees is bounded by O (log d n ) also, so that the number of empty nodes is in O ( n log d n ).
Analogously, a query traverses along O (log d n ) nodes. For the first tree T 1 , the query traverses O (log n ) nodes and therefore O (log n ) new queries have to be considered. Recursively, O (log n ) nodes in O (log n ) new trees may be traversed. In the final segment 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 segment s in the multi-level segment tree can be performed in O (log d n ) time due to the number of nodes where s appears and due to the time for visiting all these nodes. Technically, we can reinsert the segment s recursively into the multi-level segment tree.
Lemma 2.8. A WeakDelete operation for a d-dimensional multi-level segment tree for a set of n axis-parallel boxes can be performed in time O (log d n ) .
Next, we turn to the subject of orthogonal windowing queries.
EAN: N/A
Pages: 69