Hi everyone,

I have an assignment where, given a list of points in 1 dimension (that is, they are points (x,0)), to find the closest pair recursively. I've been moving along pretty well and I think I have a sound algorithm in place, but I hit a roadblock.

My algorithm finds a median and divides the list about that median, then keeps dividing it down until the list has <3 points, then it calls a method called shortest, which calculates the distance and returns a 2 element array of the closest points. But this last time i've tried it, I've gotten a nullPointerException when it calls shortest. I was wondering if any of you guys could help.

Attached is my code, ClosestPair1D.java

///////////////
//Tom George
//Problem Set 4
//1 Dimensional Closest Pair Problem
///////////////

import java.awt.Point;
import java.util.Random;
import java.util.Arrays;

public class ClosestPair1D
{
	public static void main(String[] args)
	{	//Creates random number generator, array of points, and randomly sets their
		//x and y values
		
		Random randomGen = new Random();
		Point[] points = new Point[8];
		for (int i=0; i<points.length; i++)
			points[i] = new Point(randomGen.nextInt(100),0);
		
		sortPoints(points);
		for(int i=0; i<points.length; i++)
			System.out.println(points[i]);
		for(int i=0; i<points.length-1; i++)
			System.out.println(points[i].distance(points[i+1]));
			
		Point[] closestPair = findClosestPairDC(points);
		
	}

	//Brute force Closest Pair implementation.  Scans entire array for smallest point, returns
	//a 2 element array of the closest pair of points.  Expected running time is Theta(n)
	static Point[] findClosestPairBF(Point[] points)
	{	
		Point[] closestPair = new Point[2];
		double minDistance = points[0].distance(points[1]); //assumes first 2 elements are
								  //closest pair
		for (int i=0; i<points.length-1; i++){
			if(points[i].distance(points[i+1])<minDistance){
				minDistance = points[i].distance(points[i+1]);
				Point min1 = new Point(points[i]);
				Point min2 = new Point(points[i+1]);
				closestPair[0] = min1;
				closestPair[1] = min2;
				//If it finds a smaller distance, it creates 2 points and places them
				//into the closestPair array
 			}
		}
		return closestPair;
	}

	//Divide and conquer algorithm.  Recursively divides the list about a median until the base
	//case is reached, then the lists are merged together, and the closest pair is found and 
	//returned
	static Point[] findClosestPairDC(Point[] points)
	{
		int median;
		Point[] points1, points2;
		if(points.length <=3)
			return shortest(points);
		else{
		        median = points.length/2;
			if(points.length%2 == 1)	//Checks for odd number of elements
			{
				points1 = new Point[median];
				points2 = new Point[median+1];
				for(int i=0;i<median;i++)
					points1[i] = points[i];
				for (int i=median;i<points.length; i++)
					points2[i/2] = points[i];	
			}
			else{
				 points1 = new Point[median];
				 points2 = new Point[median];
				System.out.println(points1.length+" "+points2.length);
				for(int i=0; i<median; i++)
					points1[i] = points[i];
				for (int i=median; i<points.length; i++)
					points2[i/2] = points[i];
			}

			Point [] minLeft = findClosestPairDC(points1);
			Point [] minRight = findClosestPairDC(points2);
			System.out.println(minLeft[0]+" "+minRight[1]);
		}
		
		return points;
	}
	
	//Takes an array of 3 or less points and calculates their distance, returns closest pair
	static Point[] shortest(Point[] points)
	{
		Point[] closest = new Point[2];
		double minimum = points[0].distance(points[1]);
		if(points.length < 1)
			return points;
		else{
			for(int i = 0; i<points.length-1; i++)
			{
				if(points[i].distance(points[i+1])<minimum){
					minimum = points[i].distance(points[i+1]);
					Point min1 = new Point(points[i]);
					Point min2 = new Point(points[i+1]);
					closest[0] = min1;
					closest[1] = min2;
				}
			}
		}
		return closest;
	}	
			
	
	//Making my own sort for the array because I'm apparently not clever enough to use
	//java.util.Arrays sort method.  It's a O(n^2) Insertion Sort, which sorts the points
	//by their x-coordinates.
	static void sortPoints(Point[] points)
	{
		int in,out;
		for (out = 1; out<points.length; out++)
		{
			double temp = points[out].getX();
			in = out;
			while(in>0 && points[in-1].getX() >=temp)
			{
				swap(points[in],points[in-1]);
				in--;
			}
			double temp2 = points[in].getX();
			temp2=temp;
		}
	}

	//Swaps 2 Point objects in an array
	static void swap(Point p1, Point p2)
	{
		Point temp = new Point ();
		temp.setLocation(p2.getX(), p2.getY());
		p2.setLocation(p1.getX(), p1.getY());
		p1.setLocation(temp.getX(), temp.getY());
	}
			
}

Probably a little too late but for anyone else looking through this post, the following changes should make it work:

Lines 71 and 80 should be:

points2 = points;

and also, Line 130 should be:

temp = temp2

Should ManShake answer, how much did you get for the assignment anyway? :) Code looks really good.

This article has been dead for over six months. Start a new discussion instead.