**Hello all.**

I want to implement the Shamos algorithm using java an a couple of methods.I will provide the structure of the algorithm,the methods that I need to implement and other classes that I have at my disposal.Also I will share what I've written so far and any ideas that I may have. I'm new to java,hence why I need help, but I will try and be as concise an coherent with my post as possible.Therefore I require help if possible in implementing the code .thank you

**The algorithm:**

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 . 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 δ.
->Bottom line is that,it uses a conceptual sweep line and recursion to find the closest points in the Euclidean space.

**Now the methods:**

•public static int closestPair(pointSet P).
-this does methods the preparatory work for the recursive part of the algorithm and calls the method closestPairAux for the recursive part.

•public static int closestPairAux(Point [] X, Point [] Y).
-this method carries out the recursive part of the algorithm; that is, the bulk of the work.
Other methods and classes that I can use:
-> A point is represented in the plane by an object of the class Point. This does the obvious thing; it holds the x and y coordinates as numbers so that if P is an object of type Point then P.x and P.y
->The set of input points is represented by an object of the class PointSet. As this is
a set there can be no repetition of a point and we cannot assume any ordering on the elements.

• public static PointSet getPoints(String f).
This opens a file called f and reads points from it.

• public Point nextPoint(PointSet P).
This is used to iterate over the points in P
The algorithm closestPair is implemented by the method

• public static Point closestPair(PointSet P).

1. if n = 2 then return (x1 − x2)^2 + (y1 − y2)^2
2. else
3. d ← 0
4. for i ← 1 to n − 1 do
5.... for j ← i + 1 to n do
6........ t ← (xi − xj)^2 + (yi − yj)^2
7. .........if t < d then
8. ..............d ← t
9. return d....**the closestPair algorithm**

•public static PointSet generatePoints(int n).
This returns a set of n points, whose coordinates are integers.

•public Point[] sort(char c).
This returns the points in the point set in an array sorted in non-decreasing order by coordinate as indicated by the parameter c. This parameter takes either the value ’x’ or the value ’y’, an exception UnknownSortOptionException is raised otherwise.

**This what I wrote so far:**

I decide that the first method should do the trivial case,n=<3, and then call the aux method.

 public static int closestPair(PointSet P) 
            throws TrivialClosestPairException, UnknownSortOptionException
    {
    	       int sqrDist = 0;// a method form the Poirnt class that calculate the square                              distance between this point and another point
    	       Point[] x = P.sort('x');
		Point[] x = P.sort('y');
              if (P.size() <= 3) {
			// the trivial case
			sqrDist = PointSet.naiveClosestPair(P);
			return sqrDist;
		} else {
			sqrDist = closestPairAux(x, y);
		}
		return sqrDist;
 
    }
**Is this method defined as it should?**

**An the second one:**

 public static int closestPairAux(Point[] X, Point[] Y) 
            throws TrivialClosestPairException, UnknownSortOptionException
    {
 
    }
**Which I need big time help on this one.**Any help?

**Thoughts:**

-call this method recursively, and the parameters are given as two sorted arrays, it is probably wise to divide the X array into two halves and call it recursively on each
-I shouldn't form Yv explicitely, so I guess I should iterate through all corresponding points in Y and if they are within Yv, then do the comparison for the smallest distance
-as for Y, I guess it is probably good to divide it as well, so I don't iterate through all points at each call but the divided Ys should probably contain corresponding points
like all points in Pl should also be in the corresponding half of the Y-array

**I'm new to java and any help will be great.Thank you in advance and thanks for your consideration of my post**