Hierarchical Tessellation Model and Its Use in Spatial Analysis

Paul H. Y. Tsui and Allan J. Brimicombe
School of Surveying, University of East London, Longbridge Road, Dagenham, Essex RM8 2AS, United Kingdom

Applications of hierarchical tessellation models as spatial data models for GIS have been extensively discussed in the literature for its ability of raster data compression (Gahegan, 1989 and Shaffer et al., 1990). One of the variants in this class of models which receives most attention is the quadtree (Samet, 1984). It recursively decomposes space into successively smaller quadrants until all cells contain homogeneous value or the pre-defined atomic cell level is reached. Nevertheless, the rigid tessellation structure of the quadtree is constrained by square cells and fixed decomposition ratio makes it very inflexible in modelling. The cell sizes at different levels of the quadtree are fixed by a geometric progression with common ratio 4 and hence the cell sizes are not always intuitively useful. So a generalised hierarchical tessellation model, called Adaptive Recursive Tessellations (ART) (Tsui & Brimicombe, 1992), is proposed. It relaxes both the restrictions by allowing the use of rectangular cells and variable decomposition ratios between levels. That means a much wider variety of tessellation structures are now available to users to accommodate various resolutions of data captured from different sources and for specific needs of a particular application. With ART, users can also make full use of variable resolution characteristics of the hierarchical tessellations by assigning specific sizes of cells to different levels of an ART model which is meaningful to their applications or intuitively useful. ART can be represented by a special type of two-dimensional run-encoding whose running path can vary with the tessellation structure of an individual ART model. Through the variable two-dimensional run-encoding, further data compression can be achieved.

Most of the studies on quadtree have been mainly concerned with data structure and algorithms for elementary manipulations. Though implementation of traditional deterministic spatial analyses in this context can be found in (Abel & Smith, 1984; Mark & Lauzon 1984), statistical spatial analysis of data stored in the quadtree and other hierarchical tessellation models has been rarely mentioned. In fact, the problem of integration of statistical spatial analysis in GIS has also received much attention in recent years (Bailey, 1994; Griffith, 1995). Thus another aim of this paper is to discuss methods of using spatial data stored in ART models in statistical spatial analysis. For simplicity, the quadtree is used as an illustration with the principles easily extended to the ART model with slight modification. The discussion starts with computation of the simple descriptive and summary statistics from the quadtree. Then the focus will be shifted to the relationship between spatial autocorrelation and data stored in the quadtree. In fact, hierarchical tessellation is originally a maximal blocks representation of spatial data. In it, homogeneous adjacent data has already been automatically clustered into a set of standard maximal cells pre-defined in the tessellation structure of the model. So how and what degree the spatial data clusters has been implicitly stored in hierarchical tessellation models. More detailed information on spatial arrangement and degree and pattern of clustering of the data can be obtained by the examination of the distribution of different levels of cells. Construction of connectivity weight matrix in calculation of spatial autocorrelation can also be eliminated by operation on run-encoding address of the cells. Griffith (1993) also tried to compute spatial autocorrelation on a regular square tessellation surface partitioning without explicitly building spatial weight matrix. Finally, the variable resolution characteristic of the hierarchical tessellation is also very useful in spatial analysis at variable scales. The data stored in hierarchical tessellation models can be easily aggregated into various scales pre-defined in the tessellation structure. In conclusion, hierarchical tessellation models have distinct advantages for storing data for spatial analysis.

Abel, D.J. and Smith, J.L. 1984. "A simple approach to the nearest-neighbour problem", The Australian Computer Journal, 16, 140-146.

Bailey, T.C. 1994. "A review of statistical spatial analysis in geographical information systems". In Spatial Analysis and GIS. London: Taylor & Francis Ltd. 13-44.

Gahegan, M.N. 1989. "An efficient use of quadtrees in a geographical information system", International Journal of Geographical Information Systems, 3, 201-214.

Griffith, D.A. 1993. Spatial Regression Analysis on the PC: Spatial Statistics Using SAS. Washington D.C.: Association of American Geographers.

Griffith, D.A. 1995. "Introduction: The need for spatial statistics". In Practical Handbook of Spatial Statistics. Boca Raton: CRC Press. 1-15.

Mark, D.M and Lauzon, J.P. 1984. "Linear quadtrees for geographic information systems", Proceedings of First International Symposium on Spatial Data Handling - Vol. 2, Zurich, Switzerland, July, 1984, 412-430.

Samet, H. 1984. "The quadtree and related hierarchical data structure", Computing Surveys, 16, 187-260.

Shaffer, C.A., Samet, H. and Nelson, R.C. 1990. "QUILT: A geographic information system based on quadtrees", International Journal of geographical Information Systems, 4, 103-131.

Tsui P.H.Y. and Brimicombe, A.J. 1992. "Adaptive Recursive Tessellations", Proceedings of GIS/LIS'92 - Vol. 1, San Jose, California, U.S.A., 10-12 November, 1992, 777-786.