next up previous
Next: Evaluation Up: Performance Previous: Structure Operations

Proximity Queries

The analysis of the neighbor finding routines in the Resize function is performed by calculating the number of nodes that are visited in the process. For the purpose of the Resize function only the nearest common ancestor is needed. The algorithm climbs up the tree until the lowest G-Node in the direction of the resize that is not the first or last child is returned, depending on the direction. Thus, the nodes at every other level are examined. In the worst-case, half of the nodes up the root need to be traversed, which costs O(d/2), d is the depth of the tree.

For an average case analysis, let's assume that the tree has w children at each node, and thus the depth of the tree is tex2html_wrap_inline2162 . Assume that the node is at index i and at level j. With probability tex2html_wrap_inline2168 , it is the first or last child, with probability tex2html_wrap_inline2170 it is in between. Thus, the number of nodes to be examined is as below: math1016

This can be simplified to yield tex2html_wrap_inline2172 , which is tex2html_wrap_inline2174 as j goes to infinity.

The FindWindow function makes a point query, i.e. given the coordinates of a point finds the lowest-level rectangle it encapsulates. The algorithm, starting form the root node, traverses the tree down in the hierarchy on encapsulating nodes. Assuming, that each node has w children, in the worst case it costs tex2html_wrap_inline2178 if a linear search is made when determining the overlapping window over each children nodes. Performing a binary search will be much faster especially when w is large, in which case the algorithm performs in tex2html_wrap_inline2182 , i.e. tex2html_wrap_inline2184 , actually independent on the number children on the average.



Eser Kandogan
Sun Sep 13 18:34:46 EDT 1998

Web Accessibility