ABSTRACT
Problems arising in diverse areas, such as VLSI layout design (Chapter 52), database querying (Chapter 60), robotics, and computer graphics (Chapter 54) can often be formulated as geometric intersection searching problems. In a generic instance of such a problem, a set, S, of geometric objects is to be preprocessed into a suitable data structure so that given a query object, q, we can answer efficiently questions regarding the intersection of q with the objects in S. The problem comes in four versions, depending on whether we want to report the intersected objects or simply count their number-the reporting version and the counting version, respectively-and whether S remains fixed or changes through insertion and deletion of objects-the static version and the dynamic version, respectively. In the dynamic version, which arises very often owing to the highly interactive nature of the above-mentioned applications, we wish to perform the updates more efficiently than simply recomputing the data structure from scratch after each update, while simultaneously maintaining fast query response times. We call these problems standard intersection searching problems in order to distinguish them from the generalized intersection searching problems that are the focus of this chapter. Due to their numerous applications, standard intersection searching problems have been the subject of much study and efficient solutions have been devised for many of them (see, for instance, [4, 13] and the references therein).
