Civil Engineering Reference
In-Depth Information
2
p
4
3
5
7
6
1
Figure 2.53
Squarish 2-d tree for 100 randomly generated points.
else
if (yk < y2) y2 = yk
End if
If (Qi
i
> 0) go to 1 }
In the partition of regions, if the regions are cut along their longest side instead of rotating
through the axes, the pattern and the performance of the kd-tree are quite different. The
behaviour of the kd-trees is much better as the points are more closely connected together,
and they are called
squarish kd-trees
(Devroye et al. 2000). A
squarish
2-d tree is con-
structed for 100 randomly generated points, as shown in Figure 2.53, in which the elongated
rectangles are eliminated, and the cells are much closer to a square shape. As expected, the
location of the bounding box for an arbitrarily specified point
p
takes INT(log
2
(N = 100)) +
1 = 7 steps. Starting from point 1 (root node), we go to points 2, 3, 4 and 5 as
p
is always
on the left, then to point 6 as
p
is on the right of point 5 and finally to point 7 as
p
is above
point 6.
2.7.8.2 Construction of 3-d tree
The concept and the procedure for the construction of a 2-d tree can be generalised naturally
to higher dimensions. In 3D, k = 3, the space/regions are partitioned by a plane perpen-
dicular to the x-, y- or z-axis in turn according to the level of subdivision. If Q
k
is on the
x-aligned plane, child nodes Q
2k
and Q
2k+1
are on the y-aligned plane, and the grandchild
nodes Q
4k
, Q
4k+1
, Q
4k+2
and Q
4k+3
are on the z-aligned plane and so forth. The construction
of a static kd-tree of n points takes
O
(nlog
2
(n)) time if an
O
(nlog(n)) sort is employed to
compute the median for each region subdivision. The complexity reduces to
O
(nlog(n)) if a
linear median-finding algorithm is used (Lemaire and Moreau 2000; Devroye et al. 2004).
The performance of
Algorithm kd_tree
was evaluated with 10
3
to 10
7
randomly generated
points, as shown in Table 2.8. k-d construction takes substantially more time than Quadtree
and Octree, as quick sort has to be employed to find the median for each cell subdivision. As
shown in Figure 2.49, a straight line is resulted in a plot of CPU time against Nlog(N). It is
