How to make shortest path between two points algorithm faster?

Question

I wrote this algorithm. It works (at least with my short test cases), but takes too long on larger inputs. How can I make it faster?

// Returns an array of length 2 with the two closest points to each other from the
// original array of points "arr"
private static Point2D[] getClosestPair(Point2D[] arr) 
{

    int n = arr.length;

    float min = 1.0f;
    float dist = 0.0f;
    Point2D[] ret = new Point2D[2];

    // If array only has 2 points, return array
    if (n == 2) return arr;

    // Algorithm says to brute force at 3 or lower array items
    if (n <= 3)
    {
        for (int i = 0; i < arr.length; i++)
        {
            for (int j = 0; j < arr.length; j++)
            {                   
                // If points are identical but the point is not looking 
                // at itself, return because shortest distance is 0 then 
                if (i != j && arr[i].equals(arr[j]))
                {
                    ret[0] = arr[i];
                    ret[1] = arr[j];
                    return ret;                   
                }
                // If points are not the same and current min is larger than
                // current stored distance
                else if (i != j && dist < min)
                {
                    dist = distanceSq(arr[i], arr[j]);
                    ret[0] = arr[i];
                    ret[1] = arr[j];
                    min = dist;
                }        
            }
        }

        return ret;
    }

    int halfN = n/2;

    // Left hand side
    Point2D[] LHS = Arrays.copyOfRange(arr, 0, halfN);
    // Right hand side
    Point2D[] RHS = Arrays.copyOfRange(arr, halfN, n);

    // Result of left recursion
    Point2D[] LRes = getClosestPair(LHS);
    // Result of right recursion
    Point2D[] RRes = getClosestPair(RHS);

    float LDist = distanceSq(LRes[0], LRes[1]);
    float RDist = distanceSq(RRes[0], RRes[1]);

    // Calculate minimum of both recursive results
    if (LDist > RDist)
    {
        min = RDist;
        ret[0] = RRes[0];
        ret[1] = RRes[1];
    }
    else
    {
        min = LDist;
        ret[0] = LRes[0];
        ret[1] = LRes[1];       
    }


    for (Point2D q : LHS)
    {
        // If q is close to the median line
        if ((halfN - q.getX()) < min)
        {
            for (Point2D p : RHS)
            {
                // If p is close to q
                if ((p.getX() - q.getX()) < min)
                {               
                    dist = distanceSq(q, p);        
                    if (!q.equals(p) && dist < min)
                    {
                        min = dist;
                        ret[0] = q;
                        ret[1] = p;
                    }

                }

            }
        }
    }

    return ret;
}

private static float distanceSq(Point2D p1, Point2D p2)
{
    return (float)Math.pow((p1.getX() - p2.getX()) + (p1.getY() - p2.getY()), 2);
}

I am loosely following the algorithm explained here: http://www.cs.mcgill.ca/~cs251/ClosestPair/ClosestPairDQ.html

and a different resource with pseudocode here:

http://i.imgur.com/XYDTfBl.png

I cannot change the return type of the function, or add any new arguments.

Thanks for any help!

Answer 1

There are several things you can do.

First, you can very simply cut the time the program takes to run by changing the second iteration to run only on the "reminder" points. This helps you to avoid calculating both (i,j) and (j,i) for each values. To do so, simply change:

for (int j = 0; j < arr.length; j++)

to

for (int j = i+1; j < arr.length; j++)

This will still be O(n^2) though.

You can achieve O(nlogn) time by iterating the points, and storing each in a smart data structure (kd-tree most likely). Before each insertion, find the closest point already stored in the DS (the kd-tree supports this in O(logn) time), and it is your candidate for minimal distance.