Programming Assignment 5: K-d Trees /* ***************************************************************************** * Describe the Node data type you used to implement the * 2d-tree data structure. **************************************************************************** */ /* ***************************************************************************** * Describe your method for range search in a k-d tree. **************************************************************************** */ /* ***************************************************************************** * Describe your method for nearest neighbor search in a k-d tree. **************************************************************************** */ /* ***************************************************************************** * How many nearest-neighbor calculations can your PointST implementation * perform per second for input1M.txt (1 million points), where the query * points are random points in the unit square? * * Fill in the table below, rounding each value to use one digit after * the decimal point. Use at least 1 second of CPU time. Do not use -Xint. * (Do not count the time to read the points or to build the 2d-tree.) * * Repeat the same question but with your KdTreeST implementation. * **************************************************************************** */ # calls to / CPU time = # calls to nearest() client nearest() (seconds) per second ------------------------------------------------------ PointST: KdTreeST: Note: more calls per second indicates better performance. /* ***************************************************************************** * Known bugs / limitations. **************************************************************************** */ /* ***************************************************************************** * Describe any serious problems you encountered. **************************************************************************** */ /* ***************************************************************************** * List any other comments here. Feel free to provide any feedback * on how helpful the class meeting was and on how much you learned * from doing the assignment, and whether you enjoyed doing it. **************************************************************************** */