Although in the domain of windowing systems, the amount of rectangle data (i.e. the number of windows) is not high, it is still important to examine the storage requirements and the performance of the operations analytically as it may benefit applications in other domains such as VLSI, CAD, etc., where much more rectangle data is present.

The space requirement of the Elastic Windows tree structure is the
total number of H-, G-, and L-Nodes. Since, the existence of H- and
L-Nodes are user initiated (i.e. inserted by the user), we need to
consider only the effect of G-Nodes as the additional space used by
the data structure. In the worst case, binary space partitioning is
done, as opposed to a k-ary, and the number of G-Nodes is maximum. A
worst-case analysis yields that for *n* windows, the total number of
nodes is 2*n*-1, still *O*(*n*). In the average, the structure is
expected to contain partitionings of more than 2.

Note that the primary purpose of the G-Nodes is to skip partitioning
(i.e. horizontal or vertical) at a certain level. In this case, the
maximum number of additional G-nodes is limited by the depth of the
tree structure when at every level a skip is needed which is unlikely
to occur at every branch of the tree. Still, the worst-case in this
situation is *O*(*n*).

Primary operations are insertion, deletion, structure operations (e.g. resize, move and copy hierarchy of rectangles) and proximity queries (e.g. neighbor finding and point query).

Sun Sep 13 18:34:46 EDT 1998