ABSTRACT
This chapter introduces 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, a typical stabbing query reports all segments that are stabbed by a single query line. On the other hand, a windowing query reports all objects that lie inside a window. For a set of points, a typical windowing query reports all points inside query box. The chapter describes the construction of a simple balanced one-dimensional search tree and the inductive construction algorithm of a multi-level segment tree. The kd-tree is a natural generalization of the one-dimensional search tree. It can be viewed also as a generalization of quadtrees. Range trees are defined for arbitrary dimension d and support exactly the same windowing query as the kd-tree.
