CS210 KD Trees

The purpose of this assignment is to create a symbol table data type whose keys are two-dimensional points. Well use a 2d-tree to support ecient range search (nd all the points contained in a query rectangle) and k-nearest neighbor search (nd k points that are closest to a query point). 2d-trees have numerous applications, ranging from classifying astronomical objects to computer animation to speeding up neural networks to mining data to image retrieval. See image.

Geometric Primitives To get started, use the following geometric primitives for points and axisaligned rectangles in the plane. See image.

Use the immutable data type Point2D for points in the plane. Here is the subset of its API that you may use:

public class Point2D implements Comparable < Point2D >

// Construct the point (x,y).
Point2D(double x, double y)

// x-coordinate.
double x()

// y-coordinate.
double y()

// Square of Euclidean distance between this point and that.
double distanceSquaredTo(Point2D that)

// For use in an ordered symbol table.
int compareTo(Point2D that)

// Compares two points by distance to this point.
Comparator < Point2D > DISTANCE_TO_ORDER

// Does this point equal that object?
boolean equals(Object that)

// String representation.
String toString()

Use the immutable data type RectHV for axis-aligned rectangles. Here is the subset of its API that you may use:

public class RectHV

// Construct the rectangle [xmin,xmax]×[ymin,ymax].
RectHV(double xmin , double ymin , double xmax , double ymax)

// Minimum x-coordinate of rectangle.
double xmin()

// Minimum y-coordinate of rectangle.
double ymin()

// Maximum x-coordinate of rectangle.
double xmax()

// Maximum y-coordinate of rectangle.
double ymax()

// Does this rectangle contain the point p (either inside or on boundary)?
boolean contains(Point2D p)

// Does this rectangle intersect that rectangle (at one or more points)?
boolean intersects(RectHV that)

// Square of Euclidean distance from point p to closest point in rectangle.
double distanceSquaredTo(Point2D p)

// Does this rectangle equal that object.
boolean equals(Object that)

// String representation.
String toString()

You are not allowed to modify the Point2D and RectHV types.

Symbol Table API Here is the Java interface representing the API for the symbol table data type whose keys are two-dimensional points (represented as Point2D objects):

public interface PointST < Value >

// Return true if the symbol table is empty , and false otherwise.
boolean isEmpty()

// Return the number points in the symbol table.
int size()

// Associate the value val with point p.
void put(Point2D p, Value value)

// Return the value associated with point p.
Value get(Point2D p)

// Return true if the symbol table contains the point p, and false otherwise.
boolean contains(Point2D p)

// Return all points in the symbol table.
Iterable < Point2D > points()

// Return all points in the symbol table that are inside the rectangle rect.
Iterable < Point2D > range(RectHV rect)

// Return a nearest neighbor to point p; null if the symbol table is empty.
Point2D nearest(Point2D p)

// Return k points that are closest to point p.
Iterable < Point2D > nearest(Point2D p, int k)

Problem 1. (Brute-force Implementation) Write a mutable data type BrutePointST that implements the above interface by using a red-black BST (use RedBlackTreeST that is provided).

Throw a java.lang.NullPointerException if any argument is null. Your implementation should support put(), get() and contains() in time proportional to the logarithm of the number of points in the set in the worst case; it should support points(), range(), and nearest() in time proportional to the number of points in the symbol table.

The test client (already implemented) in BrutePointST reads points from standard input and exercises the methods from BrutePointST.

$ java BrutePointST < input10K.txt
st.empty()? false
st.size() = 10000
First five values:
3380
1585
8903
4168
5971
7265
st.contains((0.661633, 0.287141))? true
st.contains((0.0, 0.0))? false
st.range([0.65, 0.68]x[0.28, 0.29]):
(0.663908, 0.285337)
(0.661633, 0.287141)
(0.671793, 0.288608)
st.nearest((0.661633, 0.287141)) = (0.663908, 0.285337)
st.nearest((0.661633, 0.287141)):
(0.663908, 0.285337)
(0.658329, 0.290039)
(0.671793, 0.288608)
(0.65471, 0.276885)
(0.668229, 0.276482)
(0.653311, 0.277389)
(0.646629, 0.288799)

Problem 2. (2d-tree Implementation) Write a mutable data type KdTreePointST that uses a 2d-tree to implement the above symbol table API. A 2d-tree is a generalization of a BST to two-dimensional keys. The idea is to build a BST with points in the nodes, using the x- and y-coordinates of the points as keys in strictly alternating sequence, starting with the x-coordinates.

• Search and insert. The algorithms for search and insert are similar to those for BSTs, but at the root we use the x-coordinate (if the point to be inserted has a smaller x-coordinate than the point at the root, go left; otherwise go right); then at the next level, we use the y-coordinate (if the point to be inserted has a smaller y-coordinate than the point in the node, go left; otherwise go right); then at the next level the x-coordinate, and so forth. See image.
• Level-order traversal. The points() method should return the points in level-order: rst the root, then all children of the root (from left/bottom to right/top), then all grandchildren of the root (from left to right), and so forth. The level-order traversal of the 2d-tree above is (0.7, 0.2), (0.5, 0.4), (0.9, 0.6), (0.2, 0.3), (0.4, 0.7).

The prime advantage of a 2d-tree over a BST is that it supports ecient implementation of range search, nearest neighbor, and k-nearest neighbor search. Each node corresponds to an axis-aligned rectangle, which encloses all of the points in its subtree. The root corresponds to the innitely large square from [(,),(+,+)]; the left and right children of the root correspond to the two rectangles split by the x-coordinate of the point at the root; and so forth.

• Range search. To nd all points contained in a given query rectangle, start at the root and recursively search for points in both subtrees using the following pruning rule: if the query rectangle does not intersect the rectangle corresponding to a node, there is no need to explore that node (or its subtrees). That is, you should search a subtree only if it might contain a point contained in the query rectangle.
• Nearest neighbor search. To nd a closest point to a given query point, start at the root and recursively search in both subtrees using the following pruning rule: if the closest point discovered so far is closer than the distance between the query point and the rectangle corresponding to a node, there is no need to explore that node (or its subtrees). That is, you should search a node only if it might contain a point that is closer than the best one found so far. The eectiveness of the pruning rule depends on quickly nding a nearby point. To do this, organize your recursive method so that when there are two possible subtrees to go down, you choose rst the subtree that is on the same side of the splitting line as the query point; the closest point found while exploring the rst subtree may enable pruning of the second subtree.
• k-nearest neighbor search. Use the technique from kd-tree nearest neighbor search described above.

Throw a java.lang.NullPointerException if any argument is null.

The test client (already implemented) in KdTreePointST reads points from standard input and exercises the methods from KdTreePointST.

$ java KdTreePointST < input10K.txt
st.empty()? false
st.size() = 10000
First five values:
0
2
1
4
3
62
st.contains((0.661633, 0.287141))? true
st.contains((0.0, 0.0))? false
st.range([0.65, 0.68]x[0.28, 0.29]):
(0.671793, 0.288608)
(0.663908, 0.285337)
(0.661633, 0.287141)
st.nearest((0.661633, 0.287141)) = (0.663908, 0.285337)
st.nearest((0.661633, 0.287141)):
(0.646629, 0.288799)
(0.653311, 0.277389)
(0.668229, 0.276482)
(0.65471, 0.276885)
(0.671793, 0.288608)
(0.658329, 0.290039)
(0.663908, 0.285337)

Interactive Clients In addition to the test clients provided in BrutePointST and KdTreePointST, you may use the following interactive client programs to test and debug your code:

• RangeSearchVisualizer reads a sequence of points from a le (specied as a command-line argument) and inserts those points into BrutePointST and KdTreePointST based symbol tables brute and kdtree respectively. Then, it performs range searches on the axis-aligned rectangles dragged by the user in the standard drawing window, and displays the points obtained from brute in red and those obtained from kdtree in blue. See image.

$ java RangeSearchVisualizer input100.txt

• NearestNeighborVisualizer reads a sequence of points from a le (specied as a command-line argument) and inserts those points into BrutePointST and KdTreeSPointT based symbol tables brute and kdtree respectively. Then, it performs k- (specied as the second command-line argument) nearest neighbor queries on the point corresponding to the location of the mouse in the standard drawing window, and displays the neighbors obtained from brute in red and those obtained from kdtree in blue. See image.

$ java NearestNeighborVisualizer input100.txt 5

• BoidSimulator is an implementation of Craig Reynolds Boids program1 to simulate the ocking behavior of birds, using a BrutePointST or KdTreePointST data type. The rst command-line argument species which data type to use (brute for BrutePointST or kdtree for KdTreePointST), the second argument species the number of boids, and the third argument species the number of friends each boid has.

$ java BoidSimulator brute 100 10