Chapter 10: Dynamization of Geometric Data Structures

Overview

In this chapter, we present a generic approach for the dynamization of an arbitrary static geometric data structure. A simple static data structure may be sufficient when the set of represented geometric objects will have only few changes over time. Static means that you have allocated a fixed amount of space. Once created, the static structure mostly has to cope with data queries due to its geometric intention . If the set of objects varies very much over time, you need to use more complex dynamic data structures that allow efficient insertion and deletion of objects. It is often easy to implement a static data structure, whereas dynamic versions of the corresponding structures are more sophisticated. We present some methods to achieve dynamization by applying general transformations to the simple static data structure.

Efficient data queries are the main feature of geometric data structures. Many geometric data structures support range queries. The output is a collection of all objects within a query area Q . More generally , we can consider search queries. That is, we are searching for all objects that fulfill a certain property with respect to a query structure Q . The presented dynamization technique requires that the search query be decomposable. That is, if we split the object set into subsets, we should be able to combine the search query results for the subsets to the overall answer. For example, the nearest -neighbor search for a query point with respect to a set of given objects represents a decomposable search query. Other examples of decomposable search queries can be found in Chapter 2.

The problem of dynamization arises if object sets change over time. For example, a one-dimensional sorted array of a fixed set of objects M is sufficient for simple x is element of M queries. But if the set M has many changes over time, a dynamic balanced AVL tree would be more efficient. In turn , the dynamic AVL tree implementation is a bit more complicated, since rotations of the tree have to be considered for the insertion of new objects and the deletion of old objects. Additionally, the AVL-tree dynamization was invented for the special case of a one-dimenional search. Simple insertions and deletions into a tree can be implemented more easily.

We want to show that it is possible to dynamize a static data structure indirectly but efficiently in a simple general setting. Once this simple generic approach is implemented, it can be used for many static data structures. The necessary requirements are fulfilled for many common range query data structures. Obviously, the generic approaches cannot be optimal against a direct dynamization adapted to a single data structure, but they are easy to implement and efficient in many applications.

Generic dynamization of geometric data structures was first introduced for insertions in [Bentley 79] and [Saxe and Bentley 79]. Later on, insertions were optimally solved in [Mehlhorn and Overmars 81]. Generic dynamization for both deletion and insertion were considered in [Maurer and Ottmann 79], [van Leeuwen and Maurer 80], [van Leeuwen and Wood 80], and [Overmars and van Leeuwen 81c]. Worst-case sensitive approaches were presented in [Overmars and van Leeuwen 81a]. The main results are collected in [van Leeuwen and Overmars 81]. For details, see also [Overmars 83]. Newer results can be found in [van Kreveld 92]. A comprehensive overview in German is given in [Klein 05]. We will use the model presented there.

In Section 10.1, we start with the example of a static kd-tree implementation and discuss the methods of generic dynamization explicitly. In Section 10.2, we formalize the given problem and define some general requirements. In Section 10.3, we present the formal methods for allowing insertion and deletion in amortized efficient time. For many applications, the given dynamization technique is already efficient enough. The dynamization technique is explained in detail, and the amortized cost complexities of the new dynamic operations are shown. Similar ideas for the worst-case sensitive approach are sketched in Section 10.4.

The effort of the dynamization itself is amortized over time. In Section 10.5, we present examples for some other decomposable search queries and apply the presented results to their known static implementations . Many of the search structures are already implemented in the CGAL library [Overmars 96]. For practical recommendations, see also Section 9.7.