## 1. INTRODUCTION

Given a N-Dimensional space we can think of this space as comprising a set of points (P) such that each element of this set comprises a N-tuple of (Cartesian) coordinates. This then allows us to also conceive of a corresponding negative space containing the set of points (N) each element if which comprises a N-tuple which includes at least one negative coordinate. For example if we have a 2-D space comprising 8x8 points then:

P = {<x,y>|-8<x<8 and -1<y<8}

N = {<x,y>|-8<x<8 and -8<y<8 and (x<0 or y<0)}

Thus we can define a spatial domain of discourse (U) such that:

```U = P disjoint_union N
```

or we can define P as:

```P = N\U
```

(The complement of the set N in the set U).

Of course the elements do not have to represent points (spatial entities that have no discernible dimension), they me represent (address) a set of uniform sub-areas into which a space in question has been divided (tesselated). This is then the fundamental idea at the heart of tesseral addressing. The distinction between Cartesian coordinates and tesseral addresses is thus that the first describe a finite point while the second describe tiles (only in the limit do they describe points).

Tesseral addressing is thus a mechanism for referencing (addressing or labelling) a N-Dimensional shape which has been sub-divided (hierarchically decomposed) into a set of isohedral (same shape) sub-spaces down to some predefined resolution. The technique was originally concerned with hierarchical clustering strategies developed in the 1960s and 1970s to improve data access times (Morton, G.M. 1996) and atomic isohedral (same shape) tiling strategies developed in the 1970s and 1980s concerned with group theory (Grunbaum and Shephard 1987). The technique was first suggested as a suitable representation for spatial applications (particularly in the domain of Geographic Information Systems - GIS) in the early 80s when ideas concerning tesseral arithmetics were first formulated (Holroyd 1983, Bell et al. 1983, Diaz and bell 1987)

With respect to N-tuple coordinate systems (such as the Cartesian coordinate system) tesseral addressing offers the following general advantages:

1. A point in a N-dimensional space can be identified by a single label instead of a N-tuple made up of N individual coordinates. (This then has implications for data storage efficiency).
2. The addressing mechanism is supported by an arithmetic (mathematically the system is a field), which in turn provides for both translation and rotation.
3. It has the effect of linearising space which in turn offers advantages of:
1. Further data storage efficiency.
2. Computational efficiency when comparing groups of addresses.
3. Computational efficiency when translating and rotating groups of addresses.
4. Addresses can be stored with attributes in a database where each address acts as a single key to data.

A N-dimensional space can be decomposed into many different forms of sub-spaces, the most common is a founded on the hyper-cube (Square in 2_D or cube in 3-D). The discussion in this document will assume this form of decomposition. We will refer to this as the quad-tesseral tessellation. Quad tesseral addressing comes in two forms: (i) hierarchical quad-tesseral addressing and (Morton) linear quad-tesseral addressing. The quad-tesseral system developed as part of the dKKBIS project is founded on the latter. We refer to this as (left-to-right) linear quad-tesseral addressing. All three approaches are described and compared below.

In general tesseral addressing systems also offer the global advantage that they can be used to model a space without reference to any specific underlying structure for data storage. Tesseral Addressing systems lend themselves to being used in many storage structures, for example B-trees (see O'Conaill 1993).

Hierarchical quad tesseral addresses (Diaz and Bell 1986, Gargantini 1983, Samet 1984) are generated in such a way as to reflect the hierarchical manner in which a subspace is decomposed (tessellated). The method of generating addresses in this manner is illustrated in Figure 1 where we consider some arbitrary 2-D positive space. We commence by assigning a tesseral address of 0 to this space. (Figure 1(a)). We then quarter this space giving each "child" quadrant a unique address to yield tiles labelled as shown in Figure 1(b). Each child address (label) is made up of a left hand symbol corresponding to its parents tesseral address and a right hand symbol corresponding to its position in relation to its siblings (i.e. 0, 1, 2 or 3). We then continue the process in a hierarchical manner by quartering these quadrants and assigning new addresses to the resulting child tiles by always appending to the right of the parent tesseral address (Figure 1(c)). We then continue in this manner (Figure 1(d)) down to some predefined resolution (depth or grain size). Points to note about the above tesselation:

• Each tesseral address associated with a tile is unique.
• All tesseral addresses (given a 2 dimensional space) are founded on the alphabet {0 .. 3}.
• The addresses 0, 00 and 000 etc. carry hierarchical depth information and should not be a confused.
• Tesseral addressing can be extended to N-dimensions (by adding further symbols).
• The system adheres to the general peano axioms.

The same process can be extended to the other quadrants of 2-D Euclidean space. However, we must identify each quadrant by associating a separate label with it. This is exactly analogous to negative coordinate addressing in the Cartesian system where the symbol "-" is used to identify such coordinates. If we label the positive quadrant with the label 0 then, so as to maintain consistency with the positioning convention used in this quadrant (Figure 1(a)), the remaining quadrants must be assigned the labels -1, -2, -3 (Figure 2(a)). We will represent these labels using a "two's complement" notation, i.e. they recur repeatedly to the left. Such digits are referred to as beaked numbers, after Diaz (1986). In this document we will represent the beaked digits, beaked 1, beaked 2 and beaked 3 using the notation "<1", "<2" and "<3". All four quadrants of Cartesian space can now be partition in the same manner as before (see Figures 2(b) and 2(c)). ### Figure 2:Tesseral addressing incorporating beaked numbers

Using the above form of addressing the depth of tessellation is encoded into the address length (where necessary leading zeros are included in the address so that the appropriate length is maintained). Consequently addresses must be stored as strings of characters of variable length. th is maintained). Alternatively, we can use some sort of bit pattern which comprises a set of bits to store an address and a further set of bits in which to store the depth (see Gahegan 1989).

The advantages of hierarchical quad-tesseral addressing compared with other tesseral systems (see below) is that large uniform spaces can be referenced by a single address while detailed spaces can be decomposed into sub-addresses and so on (see Figure 3). This then has implication with respect to data storage efficiency. The disadvantages of then system (again compared with other tesseral systems) are that translation and rotation are both complex and expensive (when implement using standard processors). ### Figure 3:Hierarchical quad-tesseral addressing allows spaces to be decomposed in a non uniform manner

Quad tesseral addresses may be stored in a quadtree data structure which serves to reflect the process of decomposition on which these addressing systems are based (see Samet 1981 and 184 for further details). This is illustrated in Figure 4. However, all the advantages offered by this data structure can equally well be incorporated into a table format (see Lauzon et al. 1985). ### 2.2 Linearisation

Given a quad tree of the form given in Figure 4 then clearly such a tree can be linearised in that it can be traversed from left to right to produce a linearisation. This is an important feature of tesseral addressing which has implications for both storage, and comparison and translation of groups of addresses.

With respect to data storage linearisation allow sequences of addresses to be stored simply in terms of the start and end address of the sequence. This is usually referred to as run-line encoding. Given such a sequence it is a trivial matter to establish whether a certain address is contained within it or not. Similarly, a sequence of addresses can be translated simply by adding/subtracting to/from the start and end addresses.

Linear quad tesseral addressing is similar to the hierarchical form described above except that that the decomposition is carried out uniformly so that all sub-spaces are decomposed down to the same level of resolution. The principal advantage of this is that the space is linearised in a uniform manner and that the superimposed arithmetic is more tractable. Such a linearisation is present in the hierarchical form however its nature is often confused (Figure 3). If we consider the space given in Figure 1(d) and assume that the addresses given represent integers to the base four it is possible to convert these numbers into decimal numbers as shown in Figure 5(a). Such numbers are referred to as Morton numbers after Morton (1966). The significance of these numbers is that they clearly indicate the linearisation (Figure 5(b)) often referred to as the Morton Linearisation. ### Figure 5:(Morton) linearisation of space

The hierarchical quad-tesseral addressing system cannot be linearised so obviously. However, if we consider the quadtree representation associated with this addressing system presented in Figure 4 then clearly such a tree can be linearised in that it can be traversed from left to right to produce a linearisation.

## 3.1. Linear Tesseral Arithmetic

Tesseral arithmetic is essentially translation, the translation distance being the number added/subtracted. Thus addition of 1 to any tile is to move a distance equivalent to the distance (and direction) that the tile 1 is from 0. For example addition of 1 to 1 moves from tile 1 to tile 10 (see Figure 1(c)). By extension tesseral subtraction is merely translation in an opposite direction. Thus we move a distance equivalent to the distance the tile is from 0 but in the direction not from zero to the tile, but the opposite direction.

The following description is based on Bell and Mason (1990); readers requiring further information are thus referred to this paper. We will first consider linear tesseral addition and then go on to consider subtraction.

To add two tesseral addresses we must make use of an addition table which produces a result for the addition of any two of the symbols used ({0 .. 3}). Such a table is given in Table 1. The construction of this table is well understood and is described in Bell et al. (1983).

0123
00123
1110312
2232021
33122130

Physically, the addition of 1 corresponds to a movement from tile 0 to tile 1, i.e. a horizontal translation of 1 tile at the relevant depth. Similarly, the addition of 2 corresponds to a vertical translation of 1 tile and the addition of 3 represents a diagonal translation. These physical interpretations must be made at a consistent depth. For example, the addition:

```3 + 1 = 12
```

corresponds to the translations 03 + 01 -> 12 and 003 + 001 -> 012, i.e. a horizontal movement of tile 03 at the resolution of Figure 1(b) or of tile 003 at the resolution of Figure 1(d).

Multi-digit addition is performed by using a carry in a fashion exactly analogous to ordinary arithmetic with numbers expressed to the base ten. Examples:

```Operands       221       113       021       013       201       210
Operations     011 +     020 +     303 +     213 +     102 +     023 +
---       ---       ---       ---       ---       ---
Answers        320       133       332       330       303       233
===       ===       ===       ===       ===       ===
Carries        11                   1        33
```

The above operations can be checked with reference to Figure 1(d). Note also that using this arithmetic we can generate addresses outside our entity space. However, for the tesseral spatial reasoning system described here, such addresses are considered to be invalid.

If desired we can produce a similar table to include the addition of beaked numbers.

### 3.1.2 Tesseral Subtraction

Subtraction is provided by an extension of the methods used for p-Adic fields (Koblitz 1977) to a given base. This is well described in Bell et al. (1986) where it is presented as follows. Given two tesseral addresses A and B, if we subtract A from B we will produce a third tesseral address X:

```B - A = X
```

or

```A + X = B
```

We find the digits for X from right to left starting with the least significant digit of X. Thus if A is equivalent to the tesseral address 021 and B is equivalent to the tesseral address 302 then the last digit of A will be 1, the last digit of B will be 2, and thus the last digit of X will be such that when we add it to 1 we get 2. From Table 1, given these figures, we can see that the last digit for X must then be 3:

```1 + 3 = 1,2
```

Thus X = --3. Removing the last digits from A, B and X and applying the carry 1 to A (with its last digit removed) we get:

```A + 1 + X = B
```

Where A, X and B represent the numbers A, B and X with their right most digits removed. Thus:

```02 + 1 + X = 30
03 + X = 30
```

The last digit of X will now be such that when we add it to 3 we get 0. From Table 1 we can see that the last digit of X must be 3:

```3 + 3 = 3,0
```

Thus X = -33. By removing the last digits from A, B and X to get ( A", B" and X") and by applying the carry 2 to A" we now get:

```A" + 3 + X" = B"
0 + 3 + X" = 3
3 + X" = 3
```

The last digit of X" will now be such that when we add it to 3 we get 3. Reference to Table 1 now demonstrates that this must be 0. Thus 302 - 021 = 033. We can test this by adding 033 to 021.

Should the result of a tesseral subtraction give a tesseral address located in one of the remaining three tiles of Cartesian space which are outside our entity space the final digit of X will repeat indefinitely. This is referred to as a beaked digit after Diaz (1986). However, given that we are only interested in the positive tile of Cartesian space in this paper we will not consider this eventuality in any further detail here.

To automate the above process we can make use of a subtraction table as shown in Table 2. This Table can then be used to "lookup" the required "X" digit and the associated carry to be added to the remaining digits of "A". The table is entered with the appropriate "B" digit along the X-axis and the associated "A" digit along the Y-axis. For each entry the carry is given first and then the "X" digit second separated by a comma.

B A 0 1 0,0 0,1 0,2 0,3 1,1 0,0 1,3 0,2 2,2 2,3 0,0 0,1 3,3 2,2 1,1 0,0

### Table 2:Subtraction Table

Examples:

```"B"       120        300        310        311        321        331
"A"         1 -        2 -        3 -      013 -      120 -      132 -
---        ---        ---        ---        ---        ---
"X"       031        122        123        122        201        023
===        ===        ===        ===        ===        ===
Carries   11         22         23         22                    22
```

Again we can check these results with reference to Figure 1(d).

### 3.2 Bit inter-leaving

From the above it can be seen that tesseral addressing does not readily support simple human interpretation. It is therefore essential that any tesseral technique also readily provides for translation to and from a more intelligible (Cartesian) coordinate system. With respect to the linear quad tesseral representation this is best achieved through a process known as bit interleaving.

We refer to the above system as Morton linear quad tesseral addressing because of the Morton linearisation that results. An essential feature if the system is that the addressing system is still founded on ideas concerning the decomposition of space into isomorphic (same shape) sub-spaces. We can dispense with this hierarchical decomposition and simply consider the addressing of some space at a particular resolution. Let us consider a 4-D space cast into a set of isohedral sub-spaces at some predetermined resolution such that each sub-space is reference by a 4-tuple of (Cartesian) coordinates and lets call these coordinates x, y z and t (time?). Let us also assume that the address is to be represented using a 32 bit signed integer. We can now assign groupings of bits within this integer as follows:

```S 4444444 33333333 22222222 11111111
```

where S is the sign bit, and the integers 1, 2, 3 and ^ 4 represent the bits to be associated with particular coordinates used to reference 4-D space. Note that:

1. The numbering has been used to indicate the relative position of each group of bits with respect to the least significant bit. The numbering does not necessarily imply that any dimensions should be associated with any particular grouping.
2. Any other distribution of bits could equally well have been allocated provided that each dimension of interest comprises a continuous sequence of bits (it is not necessary to include groupings for dimensions which are not relevant to a particular application).
3. Similarly, it is not necessary to allocate identical numbers of bits to each dimension.
4. The sign bit is included to provide for negative addressing required in order to s support various translation operations.

In order to identify the coordinate groupings a base must be allocated to each group. In the above case the following are appropriate:

```BASE1 = 1
BASE2 = 256
BASE3 = 65536
BASE4 = 16777216
```

Each base represents the integer that must be applied to a particular coordinate so that it is encoded using the appropriate grouping of bits. With respect to this document the dimensions to be associated with the BASE1, BASE2, BASE3, BASE4 groupings are labelled as X, Y, Z and T, although any other labelling could equally well have been used.

Given the above we can define a function Fcartesian2tesseral that converts its argument (a 4-tuple in this case) to a tesseral address:

```Dom(Fcartesian2tesseral) = { | The set of all  tuples}
Cod(Fcartesian2tesseral) = {a | The set of all tesseral addresses}
Gr(Fcartesian2tesseral)  = { | a = x + BASE2(y) + BASE3(z) + BASE4(t)}
```

We can define a similar function, Faddress2cartesian, to perform the reverse conversion.

The advantages offered by this approach (over other forms of tesseral addressing) are:

1. The linearisation is much more obvious than that associated with the Morton linearisation, especially when we also wish to consider negative space (Figure 6).
2. Conversion from Cartesian to tesseral addresses is much more straight forward that the bit-interleaving approach required by the Morton form.
3. Translation through the space is achieved by simple integer addition and subtraction (we do not need to resort to look-up tables). ## REFERENCES

1. Bell, S.B.M., Diaz, B.M., Holroyd, F.C. and Jackson, M.J.J. (1983). Spatially Referenced Methods of Processing Raster and Vector Data Image and Vision Computing, Vol 1, No 4, pp211-220.
2. Bell, S.B.M. and Mason, D.C. (1990). Tesseral Quarternions for the Octtree. The Computer Journal, Vol 33, No 5.
3. Diaz, B.M. (1987). Tabular Tesseral Methods and Calculators. In Diaz, B.M. and Bell, S.B.M. (Eds.), Spatial Data Processing using Tesseral Methods, Natural Environment Research Council publication, Swindon, England.
4. Diaz, B.M. and Bell, S.B.M. (1987). Spatial Data Processing using Tesseral Methods. Natural Environment Research Council publication, Swindon, England.
5. Gahegan, M.N. (1989). An efficient use of Quadtrees in a Geographical Information system. Int. Jo. of Geographical Information Systems, Vol 3, No 2, pp201-214.
6. Gargantini, I. (1983). An effective way to Represent Quadtrees. Communications of the ACM, Vol 25, No 12, pp905-910.
7. Grunbaum, B. and Shephard, G.C. (1987). Tilings and Patterns. Freeman, New York.
8. Holroyd, F.C. (1983). The Geometry of Tiling Hierarchies. Ars Combinatoria, Vol 16B, pp211-244.
9. Koblitz, N. (1977). p-Adic Numbers, p-Adic Analysis and Zeta functions. Springer-Verlag, New York.
10. Lauzon, J.P., Mark, D.M., Kikuchi, L. and Guevara, J.A. (1985). Two-Dimensional Run-encoding for Quadtree Representation. Computer vision, graphics and image processing, Vol 30, pp56-69.
11. Morton, G.M. (1966). A Computer Oriented Geodetic Data Base, and a New Technique in File Sequencing. Technical Report, IBM Canada Ltd., 1 March 1966.
12. O'Conaill, M.A., Mason, D.C. and Bell, B.M. (1993). Spatiotemporal GIS techniques for environmental Modelling. In Mather, P.M. (Ed.), Geographic Information handling - Research and Applications, John Wiley & Sons, pp103-111
13. Samet, H. (1981). An Algorithm for converting Rasters to Quadtrees. IEEE Transactions on Pattern analysis and machine Intelligence, Vol PAMI-3, No 1, pp93-95.
14. Samet, H. (1984). The Quadtree and Related Data Structures. ACM Comput. Survey, Vol 16, No 2, pp187-260.

Created and maintained by Frans Coenen. Last updated 07 January 2008