Civil Engineering Reference
In-Depth Information
about the same distance from the root. To construct a balanced kd-tree for a set of N
points, the level of subdivision, L, is given by
2
L
≥ N ⇒ L ≥ log
2
(N) ⇒ L = INT(log
2
(N)) + 1
Hence,
L
=
1
,
,
N
=
1
L
=
2
N
=
2 3
,
L
=
3
,
N
=
4 567
,,,
L
=
4
,
N
=
8 9101112
, ,
,
,
,,,,,
13 14 15 andso on.
For a more symmetrical partition of space, the line of subdivision, vertical or hori-
zontal, is rotated for each change of level of subdivision, i.e. L = 1, vertical, L = 2,
horizontal, L = 3, vertical and so forth.
2.
Sequence of points
A kd-tree can be conveniently defined by a proper sequencing of the given set of N
points,
P
= {P
i
, i = 1, N}. The following describes how a region
P
i
is divided into two sub-
regions
P
k
and
P
k+1
. Find the median from
P
i
as a pivot along the x- or y-axis depending
on the level of subdivision. Set Qi
i
= median, which divides
P
i
into
P
k
containing points
on the left of Qi
i
and
P
k+1
containing points on the right of Qi
i
. As Q
i
is the median in
region
P
i
, the number of points in
P
k
and the number of points in
P
k+1
are given by
N
−
1
N
− 1
2
i
if N is odd
i
if N is odd
i
i
2
N
=
N
=
k
k
+1
N
2
N
2
i
i
−
1
if N seven
if N seven
i
i
where N
i
= number of points in
P
i
. The subdivision will be carried out following the order
of construction of the regions. As one point, Qi,
i
, will be taken away for the subdivision of
region
P
i
, the sequence {Q
i
, i = 1, N} will be established after exactly N subdivisions.
Set
P
1
=
P
= {P
i
, i = 1, N
1
}, where N
1
= N.
P
1
will give rise to
P
2
and
P
3
, and
P
2
will
generate
P
4
and
P
5
, whereas
P
3
will generate
P
6
and
P
7
. In turn,
P
4
will generate
P
8
and
P
9
, and
P
5
will generate
P
10
and
P
11
and so on, as shown in Figure 8.25.
P
1
Q
1
Level 1
Q
2
2
Q
3
P
3
P
2
Q
5
Q
4
Q
7
3
P
5
Q
6
P
7
P
6
P
4
Q
12
Q
13
P
13
P
12
P
k
Q
k
L
k = 2
L-1
. . . 2
L
- 1
Q
2k
Q
2k+1
P
2k
P
2k+1
Figure 8.25
Sequence of sub-regions and pivots.
