The authors first draw a distinction between the data formats of raster graphics (2-dimensional arrays) and vector graphics (linked lists of line segments). The two models in turn give rise to a discussion of the well-known image space–object space dichotomy. The main purpose of the paper then becomes to consider how hierarchical data structures and algorithms are used to overcome the problems that result when the modeled graphics scene is more complex than the available display grid.

Both object-space and image-space hierarchies are discussed, although the emphasis is on image-space techniques that use quadtrees and octrees. These structures are defined, their more common forms of implementation are described, and some relevant complexity issues are presented. Vector quadtrees and vector octrees are also covered.

The second half of the paper describes the implementation of a number of basic algorithms using quadtrees. These are for pixel point location, neighboring object location, set-theoretic operations, image transformations (translation and rotation), scaling and progressive image transmission, quadtree construction, and polygon coloring.

True to its title, this paper (Part I) reviews the fundamentals of hierarchical data structures and their implementations and operations. It does so in a clear and well-illustrated manner, making reference to no fewer than 97 publications and technical reports. It is recommended reading for anyone trying to learn about quadtrees and octrees and their usefulness.

The companion paper (Part II) appeared in the July 1988 issue of the same journal. The authors describe it as covering more advanced applications, with emphasis on quadtree hidden-surface algorithms and display methods such as ray tracing and radiosity.