Project 2

Due date: Project 2 is due by 11:59:59pm on Tuesday, March 28 .
Project 2 description: project2.pdf .
Here is a small example data file of points: data.txt . When the kdtree is created to store one point at each leaf node using the command
```
 kdtree data.txt 1 < queries.txt > out1.txt
```
the output resulting from the queries in the query file queries.txt gives the resulting output of results out1.txt .
Similarly when the kdtree is created to store at most two points at each leaf node
```
   kdtree data.txt 2 < queries.txt > out2.txt
```
here is the resulting output out2.txt .

You MUST match your output format to this example output format. There will be at least a 5 point penalty if your program output does not match the example output.
Please follow the academic integrity guidelines as you work on your projects. Be sure to submit your own work. Remember that you learn the most by doing the work. We will be using software to automatically compare and detect submissions that violate the integrity guidelines.
Project Submission:
Important: Please verify you are submitting your project under the correct section. You will be penalized for submitting to an incorrect section.
- Section 2, (Wednesday 10:00-11:50am; Sage 4101), TA: Ethan Glasser-Camp
- Section 4, (Wednesday 4:00-5:50pm; Sage 2715), TA: Brandi Hill
- Section 7, (Wednesday 2:00-3:50pm; Sage 4101), TA: Vineet Chaoji

FAQ and Clarifications

Last updated 12:05pm, March 28.

One of the project tasks is to analyze the time to perform an orthogonal range query. This involves some geometric reasoning about the number of regions in the kd-tree intersected by a line. Since this may be more challenging than I intended, it is fine if you either do not answer this subpart or answer it as well as you can. You will not be penalized for not answering this subpart.
Note that you still have to analyze the time to build a kd-tree with n points.
When infinity is "defined" to be 1.0E6, VC++ outputs infinity as 1e+006, whereas the example output file has it as 1e+06. Do not worry about this difference.
The project specification says that points on the boundary of the query rectangle are considered to be inside the query region. For consistency with the way the bounding box rectangles are computed, assume that points on the right boundary or top boundary of the query rectangle must be considered to be inside the query region.
This is also consistent with the way the orthogonal ranges are described in the output file, for example as "range x= (2.5,7] y= (5,8.5]", where each interval of the rectangle is treated as a semi-open/semi-closed interval.
You should not implement all queries as some form of an orthogonal range query. You should implement each of the queries as separate queries. The logic may be similar in some cases, but you should implement them separately. You will lose points if you implement all of the queries as orthogonal range queries instantiated with different parameter values.
In particular, implementing the nearest neighbor query by repeatedly performing orthogonal range queries with rectangles of varying sizes is not a good idea. This is because it is not efficient and because the query rectangles are selected in an ad-hoc manner. You will lose points for such a solution.
While the pseudocode for Build_Kdtree mentions the set of points as a single argument, you will need to pass two vectors of points. One will be sorted by x, and the other by y. When you split the points, it will be clear how to split one of the sorted vectors. For the other vector, you can avoid resorting by performing a linear scan to identify the correct set of points based on the appropriate coordinate.
You should not repeatedly sort the point vectors at lower levels of the kd-tree as you build it. Such sorting would negatively impact the efficiency of your build function.
The STL sort algorithm permits you to specify a boolean predicate as a parameter. You can use this feature to sort points by their x coordinate (define a boolean function or function object to compare two points based on their x coordinate), or by their y coordinate (define a boolean function or function object to compare two points based on their y coordinate).
Please make sure to add comments in your code to explain your algorithms for the various queries. Well explained and easy to understand code will be graded more favorably.
For this project, you do not need to implement the copy constructor and assignment operator for the kd-tree class (or other classes you create).
When listing several data points (for example, points within a range or points that satisfy a partial match query), the output of your program should list them in order of increasing x coordinate.
If you are having trouble with the kd-tree construction step, I suggest that you run your program on a small data file with 3 to 5 points, and print all nodes of the tree in an inorder traversal. You can compare this output with your hand calculated kd-tree to identify any mistakes in your program. One potential source of errors can be incorrect calculation of the median value for the (horizontal or vertical) splits.