1
\$\begingroup\$

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
                // ...
            }
        }
    }
}
\$\endgroup\$
  • 1
    \$\begingroup\$ 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." \$\endgroup\$ – mjolka Nov 24 '14 at 9:49
  • \$\begingroup\$ 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.. \$\endgroup\$ – Andrey Tokarev Nov 24 '14 at 9:53
1
\$\begingroup\$

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;
}
|improve this answer|||||
\$\endgroup\$
  • \$\begingroup\$ 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. \$\endgroup\$ – Andrey Tokarev Nov 25 '14 at 8:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.