Java code to find the closest pair using divide and conquer

Java code to find the closest pair using divide and conquer algorithm.

Solution

The Brute force solution is O(n^2), compute the distance between each pair and return the smallest. But Devide and conquer is better and completes in O(nLogn) time.

Please find below the code:

import java.util.*;

// compile: javac ClosestPair.java
// run: Java ClosestPair 500
// Here 500 is some randomly generated set of input points.
/*
The algorithm is :
Input: An array of n points P[]
Output: The smallest distance between two points in the given array.

As a pre-processing step, input array is sorted according to x coordinates.

1) Find the middle point in the sorted array, we can take P[n/2] as middle point.

2) Divide the given array in two halves. The first subarray contains points from P[0] to P[n/2]. The second subarray contains points from P[n/2+1] to P[n-1].

3) Recursively find the smallest distances in both subarrays. Let the distances be dl and dr. Find the minimum of dl and dr. Let the minimum be d.
*/

public class ClosestPair
{
public static class Point
{
public final double x;
public final double y;

public Point(double x, double y)
{
this.x = x;
this.y = y;
}

public String toString()
{ return \"(\" + x + \", \" + y + \")\"; }
}

public static class Pair
{
public Point point1 = null;
public Point point2 = null;
public double distance = 0.0;

public Pair()
{ }

public Pair(Point point1, Point point2)
{
this.point1 = point1;
this.point2 = point2;
calcDistance();
}

public void update(Point point1, Point point2, double distance)
{
this.point1 = point1;
this.point2 = point2;
this.distance = distance;
}

public void calcDistance()
{ this.distance = distance(point1, point2); }

public String toString()
{ return point1 + \"-\" + point2 + \" : \" + distance; }
}

public static double distance(Point p1, Point p2)
{
double xdist = p2.x - p1.x;
double ydist = p2.y - p1.y;
return Math.hypot(xdist, ydist);
}

public static Pair bruteForce(List<? extends Point> points)
{
int numPoints = points.size();
if (numPoints < 2)
return null;
Pair pair = new Pair(points.get(0), points.get(1));
if (numPoints > 2)
{
for (int i = 0; i < numPoints - 1; i++)
{
Point point1 = points.get(i);
for (int j = i + 1; j < numPoints; j++)
{
Point point2 = points.get(j);
double distance = distance(point1, point2);
if (distance < pair.distance)
pair.update(point1, point2, distance);
}
}
}
return pair;
}

public static void sortByX(List<? extends Point> points)
{
Collections.sort(points, new Comparator<Point>() {
public int compare(Point point1, Point point2)
{
if (point1.x < point2.x)
return -1;
if (point1.x > point2.x)
return 1;
return 0;
}
}
);
}

public static void sortByY(List<? extends Point> points)
{
Collections.sort(points, new Comparator<Point>() {
public int compare(Point point1, Point point2)
{
if (point1.y < point2.y)
return -1;
if (point1.y > point2.y)
return 1;
return 0;
}
}
);
}

public static Pair divideAndConquer(List<? extends Point> points)
{
List<Point> pointsSortedByX = new ArrayList<Point>(points);
sortByX(pointsSortedByX);
List<Point> pointsSortedByY = new ArrayList<Point>(points);
sortByY(pointsSortedByY);
return divideAndConquer(pointsSortedByX, pointsSortedByY);
}

private static Pair divideAndConquer(List<? extends Point> pointsSortedByX, List<? extends Point> pointsSortedByY)
{
int numPoints = pointsSortedByX.size();
if (numPoints <= 3)
return bruteForce(pointsSortedByX);

int dividingIndex = numPoints >>> 1;
List<? extends Point> leftOfCenter = pointsSortedByX.subList(0, dividingIndex);
List<? extends Point> rightOfCenter = pointsSortedByX.subList(dividingIndex, numPoints);

List<Point> tempList = new ArrayList<Point>(leftOfCenter);
sortByY(tempList);
Pair closestPair = divideAndConquer(leftOfCenter, tempList);

tempList.clear();
tempList.addAll(rightOfCenter);
sortByY(tempList);
Pair closestPairRight = divideAndConquer(rightOfCenter, tempList);

if (closestPairRight.distance < closestPair.distance)
closestPair = closestPairRight;

tempList.clear();
double shortestDistance =closestPair.distance;
double centerX = rightOfCenter.get(0).x;
for (Point point : pointsSortedByY)
if (Math.abs(centerX - point.x) < shortestDistance)
tempList.add(point);

for (int i = 0; i < tempList.size() - 1; i++)
{
Point point1 = tempList.get(i);
for (int j = i + 1; j < tempList.size(); j++)
{
Point point2 = tempList.get(j);
if ((point2.y - point1.y) >= shortestDistance)
break;
double distance = distance(point1, point2);
if (distance < closestPair.distance)
{
closestPair.update(point1, point2, distance);
shortestDistance = distance;
}
}
}
return closestPair;
}

public static void main(String[] args)
{
int numPoints = (args.length == 0) ? 1000 : Integer.parseInt(args[0]);
List<Point> points = new ArrayList<Point>();
Random r = new Random();
for (int i = 0; i < numPoints; i++)
points.add(new Point(r.nextDouble(), r.nextDouble()));
System.out.println(\"Generated \" + numPoints + \" random points\");
long startTime = System.currentTimeMillis();
startTime = System.currentTimeMillis();
Pair dqClosestPair = divideAndConquer(points);
long elapsedTime = System.currentTimeMillis() - startTime;
System.out.println(\"Divide and conquer (\" + elapsedTime + \" ms): \" + dqClosestPair);
  
}
}