You cannot teach a man anything; you can only help him find it within himself. - Galileo
Tuesday, July 16, 2019
Home
Find:
Information:
Learn
Communicate
Submit
Shop
Challenges
Exploit:
Programming:
Think:
Track:
Patch:
Other:
Need Help?
Other
Members Online
Total Online: 70
Guests Online: 68
Members Online: 2

Registered Members: 116296
Latest Articles

# HellBound Hackers | Computer General | Programming

Author

## 2 Java methods and a sorting algorithm

Member Posts:
Location:
Joined: 01.01.70
Rank:
Guest
 Posted on 26-02-11 20:25
**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 x04; 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 x04; j then YV [i] x04; 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 w22; x2)^2 + (y1 w22; y2)^2
2. else
3. d u92; 0
4. for i u92; 1 to n w22; 1 do
5.... for j u92; i + 1 to n do
6........ t u92; (xi w22; xj)^2 + (yi w22; yj)^2
7. .........if t < d then
8. ..............d u92; 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.

Code
```   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:**
Code
```     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** Author

## RE: 2 Java methods and a sorting algorithm

Arabian
Banned Posts: 332
Location: inside you.
Joined: 22.09.10
Rank:
Apprentice
 Posted on 27-02-11 00:03
Code
``` public static int closestPairAux(Point[] X, Point[] Y)  throws TrivialClosestPairException, UnknownSortOptionException     {                         if (X.length<4){             return PointSet.naiveClosestPair(new PointSet (X));         }         int v = X[(int) Math.ceil(( (double) X.length/2)-1)].getX();         Point[] PL = Arrays.copyOfRange(X,(int) 0,(int) Math.ceil(X.length/2));    Point[] PR = Arrays.copyOfRange(X,(int) Math.floor(X.length/2), (int) X.length-1);                 int d = Math.min(closestPairAux(PL,Y),closestPairAux(PR,Y));         Point[] shrtDist = new Point[Y.length];             int n = 0;                       for (int i = 0; i <Y.length; i++) {                 int a = Y[i].getX();                 if ((v-a)*(v-a) <= d) {                     shrtDist[n] = Y[i];             }            }                     for (int i =0; i< shrtDist.length -1; i++) {                                 for (int r = i+1; r <shrtDist.length-1 && r< i + 7; r ++){                     d = Math.min(d, shrtDist[i].sqrDist(shrtDist[r]));                 } }         return d;         ```

Be back later. Friends havin a drag show lol xD

G'bye y'all! I was an asshole, So korg banned me.

Edited by Arabian on 27-02-11 00:05 Author

## RE: 2 Java methods and a sorting algorithm

Member Posts:
Location:
Joined: 01.01.70
Rank:
Guest
 Posted on 27-02-11 00:46
thank you for the reply....I will study the method and reply tomorrow with my understanding of it....is there something else that you recommend I should write for the first one or the second? Author

## RE: 2 Java methods and a sorting algorithm

Member Posts:
Location:
Joined: 01.01.70
Rank:
Guest
 Posted on 27-02-11 00:46
Friends havin a drag show lol xD

well have fun Edited by on 27-02-11 00:47 Author

## RE: 2 Java methods and a sorting algorithm

Arabian
Banned Posts: 332
Location: inside you.
Joined: 22.09.10
Rank:
Apprentice
 Posted on 27-02-11 00:49
Get back to you on the others lol. Despite my hatred for all things java, algorithms were kinda fun. It's a lot simpler than it seems, that's for sure, just visualize the problem, and execute. I'd recommend sitting down with a math book, too for sure X3

G'bye y'all! I was an asshole, So korg banned me.

Edited by Arabian on 27-02-11 00:49 Author

## RE: 2 Java methods and a sorting algorithm

Member Posts:
Location:
Joined: 01.01.70
Rank:
Guest
 Posted on 27-02-11 16:12
Hello wasn't here actually suppose to be X instead of Y?
Code
```Point[] shortDist = new Point[Y.length];     int n = 0;     for (int i = 0; i <Y.length; i++)         {             int A = X[i].getX();             if ((V-A)*(V-A) <= distance)                 {                     shortDist[n] = Y[i];                 }         } ```

Or was it suppose to be ?
code]Point[] shortDist = new Point[Y.length];

int n = 0;
for (int i = 0; i <Y.length; i++)
{
int A = Y[i].getY();--since V is the middle by X
if ((V-A)*(V-A) <= distance)
{
shortDist[n] = Y[i];
}
}
[/code]
Also I took your advice and picked a nice spot to try and do it myself...I dit it...and I came up with something similar....so for example imagine the code from this page but without this part

Code
```Point[] shortDist = new Point[Y.length];        int n = 0;      for (int i = 0; i <Y.length; i++) {      int A = Y[i].getX();       if ((V-A)*(V-A) <= distance)   {    shortDist[n] = Y[i];        }     }     for (int i =0; i< shortDist.length -1; i++)    {   for (int r = i+1; r <shortDist.length-1 && r< i + 7; r ++){      d = Math.min(d, shortDist[i].sqrDist(shortDist[r]));  }   }```

And I get the same result...so my questions is what was the purpose of this part of the code?Since the min is computed here
Code
`int d = Math.min(closestPairAux(PL,Y),closestPairAux(PR,Y));`

Thanks

Edited by on 27-02-11 16:21 Author

## RE: 2 Java methods and a sorting algorithm

Member Posts:
Location:
Joined: 01.01.70
Rank:
Guest
 Posted on 27-02-11 17:19
I have a method that does the following thing.
public static void getRuntimes(int p, int t, String f)
does the following:
(a) Generates p sets of points for various sizes starting from 10 (the sets are not random so
that experiments are repeatable).
(b) Finds a closest pair of points using naiveClosestPair and closestPair, and
takes the cpu times for these.
(c) Records the worst case times for each algorithm implementation taken over the p sets
(note that it is pefectly possible that the worst case runtimes for the two algorithm implementations
occur for different sets).
(d) Repeats the above with sets of size 20, 30, . . . , 10t.
(e) Outputs the result for each iteration on the file named f in the format
input-set-size naiveClosestPair-worst-case-runtime
ClosestPair-worst-case-runtime

When I create the following class
Code
```package closestPair; public class Tests {    public static void main(String [ ] args)    {              ClosestPair method = new ClosestPair();        method.getRuntimes(400, 10, "f");    }     }```

I get the error
Testing with 400 sets of 10 points .Exception in thread "main" java.lang.NullPointerException
What shoould I do.? 