10.5. Application to Search Query Data Structures

10.5. Application to Search Query Data Structures

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 )

  • image from book

  • image from book

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 )

    • image from book

    • image from book

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 )

  • image from book

  • image from book

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 )

  • image from book

  • image from book



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