| ||
For convenience, we take some simple examples from Chapter 2 and apply Theorem 10.4, thus implementing amortized insert and delete for some static data structures.
We consider data structures for orthogonal range queries, namely windowing queries and stabbing queries. The kd-tree example in Section 10.1 belongs to the point set windowing problem with a rectangular box range query in 2D. For convenience, we concentrate on BUILD, QUERY, INSERT, DELETE, and storage space. In the following, the size of the actual data set is denoted with n , whereas t denotes the length of the operation sequence.
Windowing search queries. Here, we present point set windowing queries and 2D windowing queries.
The following is a d -dimensional (point/ axis-parallel box) windowing query.
Input: A set S of points in dimension d
Query: An axis-parallel box B in dimension d
Output: All points of S in B
Data structure: d -dimensional range trees
b V ( n ) ˆˆ O ( n log ( d ˆ 1) n )
s V ( n ) ˆˆ O ( n log ( d ˆ 1) n )
q V ( n ) ˆˆ O ( k + log d n )
wd v ( n ) ˆˆ O (log ( d ˆ 1) n )
B W ( n ) ˆˆ O ( n log ( d ˆ 1) n )
S W ( n ) ˆˆ O ( n log ( d ˆ 1) n )
Q V ( n ) ˆˆ O (log ( d + 1) n )
The following is a 2D (axis-parallel box/axis-parallel box) windowing query.
Input: A set S of axis-parallel boxes in 2D
Query: An axis-parallel box B in 2D
Output: All boxes in S with elements in B
Three different search queries data structures ; see Figure 2.9:
Query box B inside: 2D segment trees ; see below
Vertices inside B : 2D range trees ; see above
Crossing segments: interval tree with 2D range tree ; see Section 2.6
b V ( n ) ˆˆ O ( n log n )
s V ( n ) ˆˆ O ( n log n )
q V ( n ) ˆˆ O (log 2 n + k )
wd v ( n ) ˆˆ O (log 2 n )
B W ( n ) ˆˆ O ( n log n )
S W ( n ) ˆˆ O ( n log n )
Q V ( n ) ˆˆ O (log 3 n + k )
Stabbing search queries. Here, we present several stabbing search queries.
The following is a 2D (line segment/line) stabbing query.
Input: A set S of line segments in 2D
Query: A vertical line l
Output: All segments of S crossed by l
Data structure: segment tree
b V ( n ) ˆˆ O ( n log n )
s V ( n ) ˆˆ O ( n log n )
q V ( n ) ˆˆ O ( k + log n )
wd v ( n ) ˆˆ O (log n )
B W ( n ) ˆˆ O ( n log n )
S W ( n ) ˆˆ O ( n log n )
Q V ( n ) ˆˆ O (log 2 n + k )
The following is a d -dimensional (axis-parallel box/point) stabbing query.
Input: A set S of d -dimensional axis-parallel boxes
Query: A point q in dimension d
Output: All boxes of B that contain q
Data structure: multi-level segment trees
b V ( n ) ˆˆ O ( n log d n )
s V ( n ) ˆˆ O ( n log d n )
q V ( n ) ˆˆ O ( k + log d n )
wd v ( n ) ˆˆ O (log d n )
B W ( n ) ˆˆ O ( n log d n )
S W ( n ) ˆˆ O ( n log d n )
Q V ( n ) ˆˆ O (log ( d + 1) n + k )