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

Question

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
                // ...
            }
        }
    }
}

Answer 1

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;
}