Chapter 2: Orthogonal Windowing and Stabbing Queries

Overview

In this chapter, we introduce some tree-based geometric data structures for answering windowing and stabbing queries. Such queries are useful in many computer graphics algorithms.

A stabbing query reports all objects that are stabbed by a single object. For a set of segments S , a typical stabbing query reports all segments that are stabbed by a single query line l . On the other hand, a windowing query reports all objects that lie inside a window. For a set of points S , a typical windowing query reports all points of S inside query box B .

We start with some simple queries and data structures, and then progress to more sophisticated queries. Furthermore, we present time and space bounds for construction and queries.

All data structures are considered to be static ; that is, we assume that the set of objects will not change over time and we do not have to consider Insert and Delete operations. Such operations might be very costly or complicated. For example, the hierarchical structure of the balanced kd-tree in Section 2.4 requires a lot of reconstruction effort if new elements are inserted or old elements are deleted.

For a dynamization, we use the simple and efficient generic dynamization techniques presented in Chapter 10. We consider simple WeakDelete operations for all data structures in order to apply the dynamization approach adequately. A WeakDelete operation marks an object as deleted; the object is not removed from the memory. After a set of efficient WeakDelete operations, it is necessary to reconstruct the complete structure; see Chapter 10 for details. The corresponding running times can be found in Section 10.5.

The presented pseudocode algorithms make use of straightforward and self-explanatory operations. For example, in Algorithm 2.2, the operation L. ListInsert( s ) indicates that the element s is inserted into the list L .

For each data structure, first, we consider the query operation. Then we give a sketch of the construction and query operations. Additionally, the corresponding algorithms are represented in pseudocode. We also give short proofs for the complexity of construction and query operations. A query is denoted by the following:

• the dimension of the space,

• a tuple (object/query object) of the corresponding objects,

• the type of the query operation.

For example, in Section 2.1, the corresponding query is denoted as a one-dimensional (interval/point) stabbing query.