but has been developed by many others, 
including Klinger and Dyer (1976), Hunter 
and Steiglitz(1979), and Samet 
(1980,1981,1984). Research into the 
theory and applications of quadtrees has 
broadened and expanded during the 1980's. 
They have become a major focus of interest 
in computer science for applications in 
image processing, graphics, robotics and 
GIS. Samet (1984) provides a comprehensive 
review of the quadtree and related 
hierarchical structures. He points out 
that there are now many different types of 
quadtree, such as the point, line, and 
regional quadtrees, that they are all 
based on the principle of recursive 
decomposition of an image but that they do 
not all share the same properties or ease 
of implementation. The efficiency of 
quadtrees for representation of regions 
and for interchangeability with more 
common representations such as vectors, 
chain codes, arrays and rasters has been 
studied intensively by computer 
scientists. 
Quadtree encoding 
A quadtree is constructed from a square 
binary array of pixels which represent an 
image. We refer to the set of black pixels 
in the image as the region. If we assume 
that an image comprises a 2 n x 2 n binary 
array of pixels, then a quadtree encoding 
represents this image by recursively sub 
dividing it into four quadrants until no 
further sub-division is necessary. This 
occurs when we obtain square blocks 
(possibly single pixels) which are 
homogeneous in value (i.e. either all 
black or all white) or when we reach the 
level of resolution that we require. This 
process is represented by a tree with four 
branches or sons in which the root node 
corresponds to the entire binary array of 
pixels or image, the four sons of the root 
node correspond to the four quadrants, 
which in our case are labelled North West, 
North East, South West and South East. The 
terminal or leaf nodes of the quadtree 
correspond to the homogeneous blocks for 
which no further sub-division is 
necessary. The nodes at level n (if any) 
represent square blocks of size 2 n x 2. 
Thus, a node at level 0 corresponds to a 
single pixel in the image, whereas a node 
at level n is the root node of the 
quadtree. An example is given to 
illustrate these concepts in Fig 1. The 
region in Fig la is represented by the 
binary array in Fig lb. The resulting 
square blocks for Fig lb are shown in Fig 
lc and the tree in Fig Id. 
Initial work on regional quadtrees was 
carried out using pointers to represent 
the tree structure. Each node was 
represented by a record which consisted of 
five pointers: four to sons, one to an 
ancestor and a field for the colour of the 
node. This technique was used by Rosenfeld 
et.al.(1982,1983,1984). Although quick 
search times may be achieved using pointer 
based structures, a large amount of 
storage is taken up by the pointers. 
According to Stewart (1986), assuming that 
each pointer uses 16 bits of memory and 
the node descriptor 8 bits, then the 
pointers take up nearly 90% of the memory 
space used. 
Regional representation using linear 
quadtrees 
Gargantini(1982) proposed a data structure 
to represent quadtrees which was more 
economical in its requirements for memory 
space. Known as a linear quadtree, it is 
in the form of a linear list consisting of 
the quadtree nodes in some order of 
traversal of the tree. A number of 
different forms of keys is available to 
map a set of ancestors to a numeric key 
(Gargantini 1982; Abel and Smith 1983). 
In our case, we follow the form proposed 
by Gargantini(1982) but number the 
quadtrants 1, 2, 3 and 4. Thus nodes are 
arranged so that the quadrants are in 
order 1,2,3,4 corresponding to the NW, NE, 
SW, SE quadrants of an image. Only black 
nodes are recorded. Thus a region in an 
image corresponds to a node which has a 
unique key derived from its ordered list 
of ancestors (Fig 2). 
Linear quadtrees offer several advantages 
over quadtrees based on use of pointers. 
Gargantini(1982) demonstrates how 
arithmetic operations on the key of the 
node can be evaluated to determine various 
properties such as determining the 
relative x, y coordinates of a node, 
adjacency of nodes, ancestor or descendent 
relationships and translation and rotation 
of images. Where disk resident quadtrees 
must be considered, the linear quadtree 
can readily be indexed to a B-tree memory 
management system to provide efficient 
access to nodes for such elemental 
operations as examinations of the 
neighbours of a given node (Abel 1984). 
IMPLEMENTATION OF GIS USING LINEAR 
QUADTREES 
As a part of a one year pilot study, we 
are developing a GIS based on linear 
quadtrees to determine its potential for 
geographical research in a range of 
different applications. Programs have been 
written in the C programming language on a 
VAX 11/750 computer running Berkeley UNIX 
4.2. 
Although we are continuing to develop and 
expand the range of functions that are 
available to the user, we have functions 
for input, manipulation, analysis and 
display of images. Input can be from 
binary array images, vector polygons or 
vector segments, the last two being 
converted to binary arrays. We are also 
implementing an algorithm for direct 
vector to quadtree encoding which was 
devised by Mark and Abel (1985). Analysis 
functions include traversing an image, 
finding the colour of a node, finding a 
neighbour to a node, finding the perimeter 
of regions, measuring distances, labelling 
the separate regions or components, 
determining geometric properties of 
regions such as size, shape or 
orientation, forming windows into an image 
at larger scales, generation of statistics 
about number of nodes, areas involved and 
correlations between geographic features 
and set logic operations on quadtrees 
(union, intersection, complement) (Mark 
and Abel, 1985). These functions allow 
users to perform the two basic operations