The R-tree [Gutt84] is an object hierarchy which is applicable to arbitrary spatial objects which is formed by aggregating their minimum bounding boxes and storing the aggregates in a tree structure. The aggregation is based, in part, on proximity of the objects or bounding boxes. The number of objects or bounding boxes that are aggregated in each node is permitted to range between m <= ceil(M /2) and M , thereby leading us to use the prefix (m,M) to characterize a particular R-tree and mirroring the effect of a B-tree. The root node in an R-tree has at least two entries unless it is a leaf node in which case it has just one entry corresponding to the bounding box of an object.
The R-tree can be constructed in either a dynamic or a static manner. The dynamic methods build the R-tree as the objects are encountered while the static methods wait until all the objects have been input before building the tree. The results of the static methods are usually characterized as being packed since knowing all of the data in advance permits each R-tree node to be filled to its capacity.
There are two principal methods of determining how to fill each R-tree node. The most natural method is to take the space occupied by the objects into account when deciding which ones to aggregate. An alternative is to order the objects prior to performing the aggregation. However, in this case, once an order has been established, there isn't really a choice as to which objects (or bounding boxes) are being aggregated. The most obvious order, although not particularly interesting or useful, is one that preserves the order in which the objects were initially encountered (i.e., objects in aggregate i have been encountered before those in aggregate i+1 ). We do not use this technique in our applet.
In this applet, all objects are assumed to be lines. There are many R-tree variants. They differ on whether the structure is built in a static or dynamic manner. In all cases, in our applet, the R-tree is built as the data is encountered. The difference between the static and dynamic methods is that the static methods rebuild the entire R-tree as each new object is added. In contrast, the dynamic methods add the new objects to the existing R-tree.
The dynamic methods differ in the techniques used to split an overflowing node during insertion. There are two types of dynamic methods. The first type has the goal of minimizing coverage and overlap. These goals are at times contradictory and thus heuristics are often used. The second type makes use of the ordering applied to the objects (actually their bounding boxes) using their centroids in our examples. They are termed nonpacked . In this case, the result is equivalent to a B+-tree and all update algorithms are B+-tree algorithms. These update algorithms do not make use of the spatial extent of the bounding boxes to determine how to split a node. Thus the goals of minimizing overlap or coverage are not part of the node splitting process although this does not preclude these methods from having good behavior with respect to these goals.
Users have the option of trying a number of different node splitting algorithms that include:
In Insert mode, click the mouse to specify a new point.
In Delete mode, delete the point nearest to the mouse at position p. The deletion occurs when the mouse is clicked. As the mouse is moved, the point that will be deleted is shown in orange.
In Window mode, click and drag the mouse to specify a query rectangle. The points that have been retrieved are shown in blue.
In Nearest mode, click to specify the query point p. All points are returned in the order of the distance from p .