3. SPACE DRIVEN PARTITION BY FILLING CURVES 
In the first case the partition take into account only the 
amount of the stored data and this quantity determines 
only the number of cells, but not their location, size and 
shape. In this approach the space filling curves, also 
called spatial ordering, can order all cell belonging to a 
regular partition. 
By definition spatial ordering is a mathematical 
transformation mapping a finite k-dimensional lattice to a 
finite set of natural numbers. 
Usually we introduce also a parameter, called resolution, 
which represents the granularity of the domain: for 
example a two dimensional spatial filling curve of 
resolution r has built by dividing the original 2D square 
representing the embedding space in 2 2r cells. 
As an example of application, we may consider the “point 
data geoidal height model layer”, which can be considered 
representative of the most of vector point data in the geoid 
data structure. We have that a point is a zero dimensional 
object and so, by the theoretical point of view it is 
impossible to find one-dimensional curve passing through 
all the point. By the way we can associate with the point 
an infinitesimal two-dimensional cell (the dimension of 
which is determined by the sample granularity in the 
sense that one point only belongs to each cell) and we 
look to a space filling curve which has the characteristic of 
completely covering the area. 
1 
3 
0 
2 
5 
7 
13 
15 
4 
6 
12 
14 
1 
3 
9 
11 
0 
2 
8 
10 
Fig. 13 -N order 
resolution 1,2 
21 
23 
29 
31 
53 
55 
61 
63 
20 
22 
28 
30 
52 
54 
60 
62 
17 
19 
25 
27 
49 
51 
57 
59 
16 
18 
24 
26 
48 
50 
56 
58 
5 
7 
13 
15 
37 
39 
45 
47 
4 
6 
12 
14 
36 
38 
44 
46 
1 
3 
9 
11 
33 
35 
41 
43 
0 
2 
8 
10 
32 
34 
40 
42 
Fig. 14 - N order 
resolution 3 
1fj 
M 
\? 
8 
Cj 
1(1 
1P 
7| 
fi 
fi 
4 
n 
1 
p 
J 
There are several space ordering, but the more important 
are the following: 
N or Peano order (Peano, 1890) (Figs. 13-14) 
n or Hilbert order (Hilbert, 1891) (Figs. 15-16) 
Both these curves pass once on every point cell in the 
two-dimensional space; moreover the points which are 
neighbours on the curve are generally neighbours in the 
space. 
In this way we can introduce an efficient single numerical 
key on a one-dimensional line for each point instead of 
identify the cells by means of two coordinates. The 
construction of the Peano key is done by the interleaving 
procedure; as an example the k key corresponding to the 
point P(6,4) with cp = 6 (in binary 0110) and X = 4 (in 
binary 0100) is k = 56 (00111000). Analogously a key for 
the Hilbert key may be otbained, even if the algorithm 
necessary for its construction it quite more complicate. 
Compared by other spatial order, for instance the more 
usual (in our approach) row order or row-prime order, 
shown in Fig. 17, it has be seen that the Hilbert curve has 
better performance in the most of spatial data processing, 
but its encoding/decoding involves tedious operations. 
In any case the suitability of the spatial ordering depends 
upon the queries applied to the data and so is useful to 
evaluate which kind of curve it is better to take into 
account by examining the particular query distribution. 
21 
22 
25 
26 
37 
38 
41 
42 
20 
23 
24 
27 
36 
39 
40 
43 
19 
18 
29 
28 
35 
34 
45 
44 
16 
17 
30 
31 
32 
33 
46 
47 
15 
12 
11 
10 
53 
52 
51 
48 
14 
13 
8 
9 
54 
55 
50 
49 
1 
2 
7 
6 
57 
56 
61 
62 
0 
3 
4 
5 
58 
59 
60 
63 
1 
2 
0 
3 
5 
6 
9 
10 
4 
7 
8 
11 
3 
2 
13 
12 
0 
1 
14 
15 
Fig. 17 - Row order and row- 
prime order