Hi

I am implementing the Shamos algorithm to find the minimum distance of two points within a set of points. Here is the algorithm:

Code :

1. If n ≤ 3 find the closest points by brute force and stop. 2. Find a vertical line V such that divides the input set into two disjoint subsets PL and PR of size as equal as possible (i.e., of size ceiling(n/2) and floor(n/2) respectively). Points to the left or on the line belong PL and points to the right or on the line belong to PR. No point belongs to both since the sets are disjoint. 3. Recursively find the distance δL of a closest pair of points in PL and the distance δR of a closest pair in PR. 4. Let δ = min(δL, δR). The distance of a pair of closest points in the input set P is either that of the points found in the recursive step (i.e., δ) or consists of the distance between a point in PL and a point in PR. (a) The only candidate points one from PL and one from PR must be in a vertical strip consisting of a line at distance δ to the left of the line V and a line at distance δ to the right of V . (b) Let YV be an array of the points within the strip sorted by non-decreasing y coordinate (i.e., if i ≤ j then YV [i] ≤ YV [j]). (c) Starting with the first point in YV and stepping trough all except the last, check the distance of this point with the next 7 points (or any that are left if there are not as many as 7). If a pair is found with distance strictly less than δ then assign this distance to δ. 5. Return δ

I am confused about how to find the closest points recursively. Here is the code that I have so far:

Code :

static int distL; static int distR; static int distLR; /** Find the square distance of the closest pairs in the point set. This static function is the preparation step for the recursive part of the algorithm defined in the method closestPairAux. */ public static int closestPair(PointSet P) throws TrivialClosestPairException, UnknownSortOptionException { Point[] X = P.sort('x'); Point[] Y = P.sort('y'); int sqrDist = 0; if (P.size() <= 3) { // Brute force sqrDist = PointSet.naiveClosestPair(P); return sqrDist; } else { sqrDist = closestPairAux(X, Y); } return sqrDist; } /** The recursive part of Shamos's Algorithm. The parameter X is an array of points sorted by the X axis and the parameter Y is the same array of points sorted by the Y axis. */ public static int closestPairAux(Point[] X, Point[] Y) throws TrivialClosestPairException, UnknownSortOptionException { Point midPoint = X[(X.length / 2)- 1]; PointSet yStrip = null; int minDist; Point[] PL = (Arrays.copyOfRange(X, 0, (int) Math.ceil(X.length/2))); Point[] PR = Arrays.copyOfRange(X, (int) Math.ceil(X.length/2), (int) X.length); Point[] YL = Arrays.copyOfRange(Y, 0, (int) Math.ceil(X.length/2)); Point[] YR = Arrays.copyOfRange(Y, (int) Math.ceil(X.length/2), (int) X.length); if (X.length > 2) { distL = closestPairAux(PL,YL); distR = closestPairAux(PR,YR); } // Find the minimum distance between left set and right set if (distL < distR) { distLR = distL; } else { distLR = distR; } for (int i = 0; i < Y.length -1; i++) { if ( Y[i].getX() - midPoint.getX() < distLR) { yStrip.addPoint(Y[i]); } } Point[] yStripsort = yStrip.sort('x'); minDist = distLR; for ( int j = 0; j <= yStripsort.length - 2; j++) { int k = j + 1; while (k <= yStripsort.length - 1 && yStripsort[k].getY() - yStripsort[j].getY() < distLR) { int d = yStripsort[j].sqrDist(yStripsort[k]); if (d < minDist) { minDist = d; } k++; } } return minDist; }

can anyone explain what I am doing wrong ?

Thanks