# Divide and Conquer Problem

Can you guys look at my code and let me know how to improve it?  I'm finding the closed set of points (X,Y) in 2D plane. I need to do it in O(n^2) and O(nlogn).  O(n^2) was easy.  My problems are on the Divide and Conquer approach.  I've been up two days trying to do it, but I can't seem to get it right.  I couldn't check my method completely because I got a null pointer exception when I sorted my array by the X-coordinate.  I'm sure I'll have more errors. Also I'm not sure if this was the correct approach, I followed this:
http://www.cs.mcgill.ca/~cs251/ClosestPair/ClosestPairDQ.html

Also how do I keep track of which points are the closest ones..... my method only return the distance between the closest points

double dL;
double dR;
double d;
double stVal = Double.POSITIVE_INFINITY;

public double closestPoints(int l, int r)
{
if((r - l) ==2){
stVal=array[0].eucDist(array[1]); //eucDist computes distance between two points
return stVal;
}
if((r-l)<2){
stVal=stVal-1;
return stVal;
}
int median = (r-l)/2;
dL = closestPoints(l, median);
dR = closestPoints(median+1, r);
double d;
if(dL<=dR)
d=dL;
else
d=dR;
Point[] Y;
int n = 0;
//next two for loops compute the number of Points with X < = than d
for(int i = median; Math.abs(array[i].getX())<=d; i--){
n++;
}
for(int i=median+1; Math.abs(array[i].getX())<=d; i++){
n++;
}
Y = new Point[n];
int index = 0;
//next two for loops fill Y with points that have X value < = than d
for(int i = median; Math.abs(array[i].getX())<=d; i--){
Y[index]=array[i];
index++;
}
for(int i=median+1; Math.abs(array[i].getX())<=d; i++){
Y[index]=array[i];
index++;
}
Arrays.sort(Y, new Point.CompY());  //sort Y by increasing Y coordinate
double dY = Double.POSITIVE_INFINITY;
for(int i=0; i<=array.length-2; i++)
{
for(int j=i+1; j<=array.length-1; j++)
{
//xx, yy initialized alreay doubles xx = Math.pow((array[i].getX()-array[j].getX()), 2);
yy = Math.pow((array[i].getY()-array[j].getY()), 2);
dY = Math.sqrt(xx+yy);
if(dY < d)
{
d = dY;

}
}
}
return d;
}

-----------------------------------------------------------

public static void main(String[] args) {

MyClass class = new MyClass("Points.txt");
Arrays.sort(driver.array, new Point.CompX());
MyClass.closestPoints(0, MyClass.array.length);
LVL 1
###### Who is Participating?
I wear a lot of hats...

"The solutions and answers provided on Experts Exchange have been extremely helpful to me over the last few years. I wear a lot of hats - Developer, Database Administrator, Help Desk, etc., so I know a lot of things but not a lot about one thing. Experts Exchange gives me answers from people who do know a lot about one thing, in a easy to use platform." -Todd S.

Commented:
>>I couldn't check my method completely because I got a null pointer exception when I sorted my array by the X-coordinate.

Author Commented:
OK I figured that I wasn't filling the array with the values. Sorry I was tired last night.  This is what I get:

Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: -1
at project.myClass.closestPoints(myClass.java:140)
at project.myClass.closestPoints(myClass.java:131)
at project.myClass.closestPoints(myClass.java:131)
at project.myClass.closestPoints(myClass.java:131)
at project.myClass.closestPoints(myClass.java:131)
at project.myClass.closestPoints(myClass.java:131)
at project.myClass.closestPoints(myClass.java:131)
at project.myClass.closestPoints(myClass.java:131)
at project.myClass.closestPoints(myClass.java:131)
at project.myClass.closestPoints(myClass.java:131)
at project.FindPoints.main(closestPoints.java:14)

where line 131:
dL = closestPoints(l, median);
line 140:
dR = fcp(median+1, r);

line 14 on main class
myClass.closestPoints(0, myClass.array.length);
Commented:
>>myClass.array.length

Any attempt to index a Java array at array.length will fail since array[array.length - 1] is the upper bound. Is that what you're doing?

Experts Exchange Solution brought to you by