Taxonomy of space tessellation

When we map an area or create a digital database for it, the first task is often to partition the space into smaller units. There are traditionally two methods of partitioning: vector and raster. A vector partition delineates the boundary of features by polylines while a raster partition subdivides the space into a regular matrix of square or rectangular pixels. These two are complementary methods of subdividing the space either by features or by unconstrained space cells. In the third dimension, they are extended to polyhedra and voxels, respectively. We will argue in this paper that the terms 'vector' and 'raster' cannot describe all cases of tessellation. With advances in data modelling, variations of the two traditional methods have been developed, such as the representation of a feature by pixels and not by polylines. At present, there is a lack of systematic terminology to describe the various methods of tessellation. In this paper, we will propose a taxonomy for three-dimensional space tessellation. Its essential feature is to distinguish between abstract concepts of tessellation and their encoding methods. We recognise that tessellation of geographic space is carried out in different stages with increasingly precise mathematical meaning. This provides us with an insight into the process of spatial tessellation and a model to systematically describe the various structures. These concepts could form a basis for spatial data models. (C) 2000 Elsevier Science B.V.