This homework is based on k-d trees, explained in Winston, ch. 19, pp. 403-408. (
To complete the assignment, you only need to consider 2-d trees (viz. k is 2 throughout).
A k-d tree program normally has two parts: (i) build a tree from a given set of data points and (ii) query that tree with a new data point. The tree in part (i) is not dynamic; it never changes once it is built.
The goal of the homework is to query a 2-d tree (built with data from figure 19.2) with several unknowns (U). For each unknown you have to find the nearest neighbor using the Euclidean metric and report it (its color). Thus, the input is the set of points given in the aforementioned figure. Then an unknown point is entered and the program reports the color of its nearest neighbor.
Make sure that your program is able to single-step its calculations. Essentially, such a trace tells us which parts of the decision tree (cf. Figure 19.7) the program is visiting until it finds the answer.
Here’s a list of query points (unknowns) that you have to use to test your program. It is crucial to notice that the first coordinate is the width and the second coordinate is the height.
• U(1,4)
This is the unknown analyzed in ch. 19 (answer: orange block at (2,5))
• ) U(1,1)
• =) U(6,6)
• U(6,1)
• U(w,h), where w and h are integers belonging to the closed interval [1,6]
