Civil Engineering Reference
In-Depth Information
Figure 8.26
A
squarish
2d-tree.
Let's consider the relationship of the points in the sequence {Q
k
, k = 1, N
+
} associated
with region subdivisions,
P
1
,
P
2
, …,
P
N
, where N
+
= 2
L
− 1 ≥ N. Q
1
is the root node,
which has child nodes Q
2
and Q
3
and in general, Q
k
generates Q
2k
and Q
2k+1
. Hence,
Q
2k
and Q
2k+1
are the children of Q
k
, and Q
k
is the father of Q
2k
and Q
2k+1
, as shown
in Figure 8.25. Hence, Q
k/2
is the father node of Q
k
, and in case k/2 = 0 or k=1, Q
k
is
already at the top of the tree. Generalising the previous results, the grandfather (two
levels up) of Q
k
is given by Q
k/4
, etc.
Let's now consider the construction of the 2d-tree for 15 points, as shown in Figure
8.24. The median in the x-value of the given 15 points is determined and is assigned to Q
1
.
Points sorted to the left of the median are put to region
P
2
, and points sorted to the right
of the median are put to region
P
3
. The process continues with the subdivision of
P
2
and
P
3
along the y-axis to give rise to points Q
2
and Q
3
and regions
P
4
,
P
5
,
P
6
and
P
7
. Subdivision
of regions
P
4
,
P
5
,
P
6
and
P
7
will generate points Q
4
, Q
5
, Q
6
and Q
7
and regions
P
8
,
P
9
,
P
10
,
P
11
,
P
12
,
P
13
,
P
14
and
P
15
. At this stage, there is exactly one point in each region
P
8
to
P
15
,
which are assigned to Q
8
to Q
15
, and the construction of the 2d-tree is completed.
The concept and the procedure for the construction of 2d-tree can be generalised natu-
rally to higher dimensions. In three dimensions, k = 3, the space/regions are partitioned
by a plane perpendicular to 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
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 k-d 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 (see Section 2.7.8). The
complexity becomes
O
(nlog(n)) if a linear median finding algorithm is used (Lemaire and
Moreau 2000). 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 points are more closely
grouped together, and they are called
squarish
kd-tree, as shown in Figure 8.26.
8.2.3.2 Kd-tree partition of points
A nice feature of kd-tree partition is that at any level of subdivision, each region contains
roughly an equal number of points irrespective of the point distribution. In triangulation,
