# Nearest point using 2D tree, static variable for the closest point so far

This is a problem from a Coursera class:

Write a data type to represent a set of points in the unit square (all points have x- and y-coordinates between 0 and 1) using a 2D tree to support efficient nearest neighbor search (find a closest point to a query point).

I implemented the class with pre-setup API. The problem for me was to efficiently realize the pruning rule:

To find 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).

So I need to store statically best tuple (closest point, minimum distance) so far. For this purpose I think static variable of class is not the best choice (it is needed only for one this method). I also don't like my solution for this: I made nested static class, pointDist, with static variables. What is a more optimal/elegant decision?

public class KdTree {

private Node root;
private int size;

public KdTree() {
root = null;
size = 0;
}

// ... other class methods

private static final class pointDist {
private static Point2D p; // closest point
private static double d; // min distance

private static void begin() {
p = null;
d = Double.POSITIVE_INFINITY;
}
}

private void nearest(Point2D p, Node x) {
if (x == null) return;
// code with p, x, pointDist.p and pointDist.d variables
// ...
}

public Point2D nearest(Point2D p) {
assert size() > 0;
pointDist.begin();
nearest(p, root);
return pointDist.p;
}

private static class Node {

private Point2D p; // the point
private RectHV rect; // the axis-aligned rectangle corresponding to this node
private Node lb; // the left/bottom subtree
private Node rt; // the right/top subtree

public Node(Point2D pp, Node prevN, int caseCut) {
p = pp;
lb = null;
rt = null;
// root case
if (caseCut == -1) rect = new RectHV(0, 0, 1, 1);
else {
RectHV prevR = prevN.rect;
// the rest of the code here is to define rect based on values of
// caseCut variable: 0,1,2,4 - cuts from left, right, bottom and top
// ...
}
}
}
}

• This is in violation of Coursera's honor code "I will not make solutions to homework, quizzes or exams available to anyone else. This includes both solutions written by me, as well as any official solutions provided by the course staff." – mjolka Nov 24 '14 at 9:49
• For this purpose, I intentionally removed all other methods and didn't name the Coursera class. So in this version, it is not a complete solution at all. Moreover, the deadline for this problem passed couple weeks ago. Finally, I can remove this post after receiving comments.. – Andrey Tokarev Nov 24 '14 at 9:53

You're right in sensing there has to be a better way to do this. Right now, you're setting static fields from within instance methods, which is rarely a good idea. Luckily, your code is already sufficiently structured that fixing this requires very little work.

Explicitly pass an instance containing a Point2D and double as a parameter in the nearest method. This keeps your algorithm as it is, but it limits the scope of changes so that they stay within local execution:

private static final class PointDistance {
// note that these are not static
Point2D p;
double d;
}

private void nearest(Point2D p, Node x, PointDistance closest) {
// replace pointDist with closest here
}

public Point2D nearest(Point2D p) {
final PointDistance closest = new PointDistance();
nearest(p, root, closest);
return closest.p;
}

• Thanks @JvR ! It does work, looks much better, and is more correct realization as I understand. Somehow I was afraid that if class members would not be static, they would be duplicated in every recursive call. Now, because of your code, I realize that though they are passed by value, its value is a reference, meaning that all recursive calls work with the same object - that's what I need. – Andrey Tokarev Nov 25 '14 at 8:18