Due 5/25/99

In this problem we will examine another application of k-d trees.  In this case we would like to design an algorithm that finds the nearest point to a query line.  See the figure below. We would like to do this while searching a few points in the tree as possible.   For simplicity we will work in two dimensions.  The k-d tree has nodes with fields: axis, value, left, right, and point.  A leaf is indicated by left = right = null.  A point is a structure with two fields: x and y.  A query is specified by two numbers (a,b) where the query line is the solutions to the equation ax + b = y.  The distance between a point p and a line r is the distance between the point and the line measured on the line through the point p and perpendicular to the line r.

In the k-d tree, each node defines a rectangle in the plane.  The root is the entire plane.  If the root.axis = x and root.value = c then the left child of the root defines the half plane defined by x <= c and the right child defines the half plane defined by x > c.  Generally, if a node n defines a rectangle x1 < x <=  x2, y1 < y <= y2, n.axis = y and n.value = c then the left child defines the rectangle x1 < x <=  x2, y1 < y <= c and the right child defines the rectangle x1 < x <=  x2,  c < y <= y2.  It will be important in your algorithm to know the rectangle defined by each node of the tree when it is being considered for a search.

Your algorithm design should include well documented pseudo code.  You should include a small illustrative example how the algorithm works.   Your algorithm should not search the entire tree unless it has to.

                query line
-----------------------------------------
|           o    /                       |
|               /           o            |
|    o         /                         |
|             /               o          |
|            /                           |
|           /   o closest point   o      |
|    o     /                             |
|         /              o               |
|        /     o                         |
|  o    /                                |
|      /                                 |
|     /              o           o       |
|    /         o                         |
|   /                                    |
-----------------------------------------