entified 
Morton 
nt (FP). 
1 Of the 
| space. 
codes is 
| query 
nts, the 
ake on 
e fora 
ry time 
n [A] is 
| that in 
evels of 
nerally 
gorithm 
ides are 
This is 
operties 
n codes 
ace are 
vindow 
. corner 
and the 
st code. 
ing of 
s which 
indows 
rdinate 
earches 
gure 1b 
ould be 
ove the 
ı time. 
multi- 
sible to 
nains of 
llection 
] by an 
., Wn} 
an n-d 
space 
riety of 
d to as 
92]. In 
an bear 
utes are 
lues for 
n-d co- 
One can draw an analogy between the 2-d and 
the n-d case. An n-d query window is a solid 
figure composed of hypersurfaces. The 
analogy is to order the n-d space and search in 
the hypersurfaces (instead of along the edges, in 
the 2-d case) for the next data point in the 
window. The optimization of this search would 
involve, in the least, the determination of all 
possible faces in which the entry point could be 
  
—— 
b 
| l 
| | 
[D 
| l 
  
rro quy rm 
| l— J 5 - 
| [All @ 
| | 
  
  
  
  
  
  
  
  
  
  
(a) Influence of Location 
of Query Window 
Fig. 1 
These problems, that have been identified with 
range search based on Morton ordering, 
generate a need to explore some other ordering 
schemes which has, at least, the simplicity of 
Morton order, and at the same time can offer 
some advantages for extending the 2-d search 
Concept to n-d search. 
4. THE LAYERED APPROACH SOLUTION 
AND SPACE ORDERING 
To benefit from the simplicity of the 2-d range 
search algorithm, the concept can be extended to 
the n-d case. The n-d space is treated as a 
collection of 2-d layers. Points in each layer are 
consecutively coded, starting from the south- 
west corner of the basic or first layer (the x-y 
plane). All subsequent layers are then a 
projection of each layer on the x-y plane. The 
Coding of points within these layers is done in 
Such a way that the south-west corner of the 
first layer is given the code 0, and all the points 
within the layer are completely ordered until the 
north-east corner point, which has the 
maximum code in that layer. The code of the 
south-west corner of any succeeding layer is 
Sg to the maximum code in the previous layer 
plus 1. 
99 
found, and searching in these faces to find the 
first points. Doing this would require complex 
analysis, because of the complexity of 
hypersurfaces. It has already been shown in the 
2-d algorithm that the cost of the search is 
highest in the optimization which finds the first 
points. With the complexity of hypersurfaces, 
the time for finding the FP's may be extremely 
high. 
  
  
  
  
  
  
  
  
  
(b) Over-head in a 
Rotated Window 
The Morton code in the entire application space 
are not automatically sorted by layer. In other 
words, a Morton curve does not completely 
traverse a layer before visiting another one. 
Instead it goes in and out of any given layer, 
depending on the size of the resolution units in 
every dimension greater than 2. This fact is 
demonstrated in Figure 2, using a 3-d space as 
an example. As a consequence, it is difficult, if 
at all possible, to apply the same technique of 
search optimization on Morton codes. 
The row order which does not seem to impose 
the same restriction in coding and optimization 
has been investigated, as an alternative to 
Morton order, in the solution of n-d range 
search. The row order completely traverses a 
layer before going into another layer (see Figure 
3). Other properties of the row order are that: 
the codes are always sorted in increasing y-co- 
ordinates, even on profiles not parallel to the co- 
ordinate axes; it is also always sorted in x-co- 
ordinates, given any constant y-value. 
Due to the properties of row order, it seems to 
allow better optimization of n-d range search. 
Apart from being compatible with the layered 
approach, it also makes the determination of the 
first points (FP's) much easier than in the case 
of Morton order. (Recall that the most time is 
spent on the determination of the FP's in the 2-d 
algorithm using Morton order.) This is