next up previous
Next: Elastic Windows Data Structures Up: Data Structures and Algorithms Previous: Problem Domain

Existing Data Structures

Hierarchical spatial data structure techniques can be first examined according to the partitioning [81]. Space-based partitioning organize the embedding space from which the data is drawn such as the grid file [82], PR quadtree [83], MX-CIF quadtree [84], PM quadtree [85], PMR quadtree [86], etc. Data-based partitioning organizes the data to be stored such as the point quadtree [87], k-d tree [88], R-Tree [89], etc.

One way of representing rectangle data is to map it onto a higher-dimensional point data and use point-based data structure techniques such as the grid file, PR quadtree, point quadtree, and k-d-tree. Mapping of the rectangular data to a four-dimensional point can be done in a number ways such as x and y coordinates of the opposite corners, or x and y coordinates of one corner and the width and height, etc. Point-based representations of rectangular data have the drawback that they lack to benefit from the locality of data for the efficiency of both storage and spatial operations.

Rectangle data can also be represented in terms of the lines it is composed of and line-based data structure techniques such as PM quadtree, PMR quadtree, etc. Line-based representations of rectangular data had the drawback that a spatial operation specified in terms of its line segments may not satisfy the conditions of the operation yet the rectangle they are composed of satisfies them.

Rectangle data can also be represented in terms of the area it occupies. Techniques such as MX-CIF quadtrees and R-Trees organize rectangle data in hierarchical groupings of minimum bounding boxes. In MX-CIF quadtree uses space-based quadtree partitioning where each rectangle is associated with its minimum enclosing quadtree block. In R-Trees rectangle data is partitioned into hierarchically nested minimum bounded boxes. R-Trees have the drawback that there locality of data is not utilized.

Let's examine these techniques based on the characteristics of the problem domain. In most of the above techniques, the rectangular data is assumed to be at the same level, i.e. there are no hierarchical relationship among rectangles. Yet, for most of the techniques imposing such a relationship is trivial. Such as in R-Trees all that is needed is to mark such rectangles as hierarchy nodes and take special action for such nodes when reorganization is performed on the R-Tree. For the others it may be necessary to add pointers for the representation of hierarchical relationships.

Most of the above techniques do not assume any layout strategies. Thus, they can be applied to overlapping as well as non-overlapping layouts. Yet, the performance of the algorithms can be improved when the problem domain enforces a specific layout strategy such as space-filling layouts. For example, point-based techniques such as k-d-trees can be adopted to suit space-filling layouts where each point is considered as the boundary between rectangles.

Dynamic nature of the layout is critical in the selection of the data structure technique. Space-based partitioning techniques do not perform efficiently when the layout is dynamically changing affecting a number of rectangles. For example, an elastic resize operation may result in considerable reorganization when MX-CIF quadtree is used (Figure gif). This is not the case in most of the data-based partitioning such as R-Trees, since these techniques represent the spatial relationships among the data not the space they are organized in.


Most of the data structures and algorithms in the domain of window management are for independent overlapping window strategies [90, 91], hence they support neither hierarchical nesting nor dynamics that affect a number of windows on the screen.

However, in other domains such as graph layout drawing, interface design and VLSI layout tools, there exist algorithms that deal with more complicated dynamics. In the domain of graph layout drawing algorithms typically focus on producing layouts to optimize criteria such as total number of link crossings, total diagram area, etc. [92]. Kosak et al. [93] proposed a constraint-based heuristic algorithm where visual organization rules define the constraints on the layout. Ioannidis proposed an algorithm for non-overlapping objects at multiple granularities [94].

Tcl/Tk provides a number of geometry managers (e.g. pack, grid, etc.) that determine the layout of the graphical interface widgets. Geometry managers allow hierarchical nesting of widgets and allow layout reorganizations that affect multiple widgets.

Ousterhout [95] proposed a corner-stitching data structuring technique for VLSI layouts, where corners of rectangular areas are connected to each other. Proposed data structure enables operations like finding neighbors efficiently, however, overlapping and hierarchical rectangles are not supported, and moving/resizing rectangles are costly since connections must be updated. Samet [81] has an excellent review of data structures and algorithms for handling collections of small rectangles.

next up previous
Next: Elastic Windows Data Structures Up: Data Structures and Algorithms Previous: Problem Domain

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

Web Accessibility