Solved

# Divide and Conquer Problem

Posted on 2008-11-17
854 Views
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);
``````
0
Question by:ubuntuguy

LVL 86

Expert Comment

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

0

LVL 1

Author Comment

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);
0

LVL 86

Accepted Solution

>>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?
0

LVL 1

Author Comment

No I actually I changed it to array.length-1.  I still get the same error.
0

## Featured Post

By the end of 1980s, object oriented programming using languages like C++, Simula69 and ObjectPascal gained momentum. It looked like programmers finally found the perfect language. C++ successfully combined the object oriented principles of Simula w…
This was posted to the Netbeans forum a Feb, 2010 and I also sent it to Verisign. Who didn't help much in my struggles to get my application signed. ------------------------- Start The idea here is to target your cell phones with the correct…
Viewers learn how to read error messages and identify possible mistakes that could cause hours of frustration. Coding is as much about debugging your code as it is about writing it. Define Error Message: Line Numbers: Type of Error: Break Down…
Viewers will learn about the different types of variables in Java and how to declare them. Decide the type of variable desired: Put the keyword corresponding to the type of variable in front of the variable name: Use the equal sign to assign a v…