Exercise C: k-d Trees

Objectives

to understand the algorithm used to add to a k-d tree
to understand the algorithm to build balanced k-d trees
to understand the algorithm for finding nearest neighnbors in a k-d tree

Exercises

For the list of points $(12.0, 8.0), (18.0, 11.0), (15.0, 15.0), (8.0, 12.0), (3.0, 18.0), (10.0, 1.0)\ , (17.0, 5.0)$

add them one by one in the order given to a k-d tree;
build a balanced k-d tree, showing the list of points sorted by x-coordinate and the list of points sorted by y-coordinate passed to each level in the recursive worst-case $O(n \log n)$ algorithm for building a balanced k-d tree (when building a tree with an even number of nodes, make the left subtree have one less node than the right);
for each node in the k-d trees built in the previous steps, find the rectangular region such that any additional points added to the subtree must be in that region;
show which subtrees are not explored by the nearest neighbor algorithm when searching for the nearest neighbor of (4, 5).
Repeat the above for the list of points $(6.0, 3.0), (2.0, 17.0), (15.0, 20.0), (2.0, 3.0), (17.0, 13.0), (3.0, 9.0), (10.0, 11.0), (7.0, 7.0), (9.0, 12.0), (16.0, 11.0), (15.0, 2.0), (19.0, 4.0)$.

Solution for 1st List of Points

After adding points one by one (rotate 90 degrees clockwise) for top-down
view.
2               (15.0, 15.0)
1        (18.0, 11.0)
2               (17.0,  5.0)
0 (12.0,  8.0)
2               ( 3.0, 18.0)
1        ( 8.0, 12.0)
2               (10.0,  1.0)

Regions for each node
2 (15.0, 15.0) [(12.0, 11.0)-(inf, inf)]
1 (18.0, 11.0) [(12.0, -inf)-(inf, inf)]
2 (17.0, 5.0) [(12.0, -inf)-(inf, 11.0)]
0 (12.0, 8.0) [(-inf, -inf)-(inf, inf)]
2 (3.0, 18.0) [(-inf, 12.0)-(12.0, inf)]
1 (8.0, 12.0) [(-inf, -inf)-(12.0, inf)]
2 (10.0, 1.0) [(-inf, -inf)-(12.0, 12.0)]

Building the balanced tree
X: [(3.0, 18.0), (8.0, 12.0), (10.0, 1.0), (12.0, 8.0), (15.0, 15.0), (17.0, 5.0), (18.0, 11.0)]
Y: [(10.0, 1.0), (17.0, 5.0), (12.0, 8.0), (18.0, 11.0), (8.0, 12.0), (15.0, 15.0), (3.0, 18.0)]
selecting (12.0, 8.0) as the root

left subtree
Y: [(10.0, 1.0), (8.0, 12.0), (3.0, 18.0)]
X: [(3.0, 18.0), (8.0, 12.0), (10.0, 1.0)]
selecting (8.0, 12.0) as the root

left left subtree
X: [(10.0, 1.0)]
Y: [(10.0, 1.0)]
selecting (10.0, 1.0) as the root

left right subtree
X: [(3.0, 18.0)]
Y: [(3.0, 18.0)]
selecting (3.0, 18.0) as the root

right subtree
Y: [(17.0, 5.0), (18.0, 11.0), (15.0, 15.0)]
X: [(15.0, 15.0), (17.0, 5.0), (18.0, 11.0)]
selecting (18.0, 11.0) as the root

right left subtree
X: [(17.0, 5.0)]
Y: [(17.0, 5.0)]
selecting (17.0, 5.0) as the root

right right subtree
X: [(15.0, 15.0)]
Y: [(15.0, 15.0)]
selecting (15.0, 15.0) as the root

Built Tree
2               (15.0, 15.0)
1        (18.0, 11.0)
2               (17.0,  5.0)
0 (12.0,  8.0)
2               ( 3.0, 18.0)
1        ( 8.0, 12.0)
2               (10.0,  1.0)

Regions for each node
2 (15.0, 15.0) [(12.0, 11.0)-(inf, inf)]
1 (18.0, 11.0) [(12.0, -inf)-(inf, inf)]
2 (17.0, 5.0) [(12.0, -inf)-(inf, 11.0)]
0 (12.0, 8.0) [(-inf, -inf)-(inf, inf)]
2 (3.0, 18.0) [(-inf, 12.0)-(12.0, inf)]
1 (8.0, 12.0) [(-inf, -inf)-(12.0, inf)]
2 (10.0, 1.0) [(-inf, -inf)-(12.0, 12.0)]



not exploring subtree (18.0, 11.0) with region (12.0, -inf)-(inf, inf)
        distance from (4.0, 5.0) to best so far (10.0, 1.0) is 7.211103
        minimum distance to this subtree's region is 8.000000

7.211103
(10.0, 1.0)

Solution for 2nd List of Points

Run the executable /c/cs223/hw5/KDTreeExamples with first command-line argument equal to the integer sum of the x- and y-coordinates of the left-left grandchild of the root when building a balanced k-d tree from the 2nd list of points and making the left subtree contain one less point than the right subtree in subtrees that contain an even number of points. The second command-line argument is 2 and the third is either --add, --build, or --nearest where --nearest is followed by the point you want to find the nearest neighbor of.

/c/cs223/hw5/KDTreeExamples password 2 --add
/c/cs223/hw5/KDTreeExamples password 2 --build
/c/cs223/hw5/KDTreeExamples password 2 --nearest 4 5

Run with no arguments to see other options.