import java.util.*;
//You may assume that all Points are unique.
public class PointSet {

	private ArrayList<Point> list;

	private Comparator<Point> compareMethod;

	//default constructor
	public PointSet(){

		list = new ArrayList<Point>();

	//copy constructor for a point
	public PointSet(PointSet l){

		list = new ArrayList<Point>();
		for(Point p: l.list){

	//randomly generating a Point to add to the PointSet based on the parameter ranges
	public PointSet(int xMax, int yMax, int num){

		list = new ArrayList<Point>();
		Random r = new Random();

		for(int i = 1; i <= num; i++){

			int x = r.nextInt(xMax + 1);
			int y = r.nextInt(yMax + 1);
			this.add(new Point(x,y));


	//number of elements in the list
	public int numElements(){

		return list.size();

	//checks if list has no Points
	public boolean isEmpty(){

		return (list.size() == 0);

	//checks if list contains specific point
	public boolean contains(Point p){

		return list.contains(p);

	//returns a Point at a given index
	public Point get(int index){

		if(index < 0 || index > list.size()-1){
			throw new IndexOutOfBoundsException("problem with index");
		return list.get(index);

	//adds a point to Pointset
	public void add(Point p){


	//removes a point from PointSet
	public void remove(Point p){


	//string representation
	public String toString(){
		String temp="";
		for(Point p: list){
			temp+= p.toString();
		return temp;

	//adds all Points from a set in this PointSet
	public PointSet merge(PointSet set){

		PointSet ret = new PointSet(set);
		for(Point p: list){

		return ret;

	//Creates  pointset with the Points that this set and the parameter have in common
	public PointSet intersection(PointSet set){

		PointSet ret = new PointSet();
		for(Point p : list){
		return ret;

	/*This will examine all the different combinations of point pairs within the calling object 
	 * and determine which pairs of points have the smallest distance.  This will build and return 
	 * a PointPairSet of all PointPairs with the closest distance.  This method will run in
	 * quadratic time. Assume that the PointPairSetĂ­s add method is constant time. */
	public PointPairSet closestPointBF(){

		PointPairSet smallestDistances = new PointPairSet();//set of smallest pairs to return
		PointPair closestPair=new PointPair(new Point(0,0), new Point(Integer.MAX_VALUE,Integer.MAX_VALUE));

		double minDist = Integer.MAX_VALUE;
		for(int i =0; i < this.list.size(); i++){
			for(int j =0; j<this.list.size(); j++){
				PointPair compare = new PointPair(this.list.get(i),this.list.get(j));//two points to compare 
				//not comparing the point to itself, distance between the two points is smaller than distance with
				//any other point so far
				if(i != j && compare.distance() < minDist){
					minDist = compare.distance();//that distance is now saved as smallest
					closestPair = new PointPair(this.list.get(i), this.list.get(j));
			minDist= Integer.MAX_VALUE;//RESET

			smallestDistances.add(closestPair);//add small distance pair

		return smallestDistances;

	//returns a set of points with closest distance using ologn runtime
	public PointPairSet closestPointsDC(){

		qsort(0);//nlogn time
		PointSet sortedX = new PointSet(this);
		PointSet sortedY = new PointSet(this);

		return closestPoints(sortedX, sortedY, 0, this.list.size());

	private PointPairSet closestPoints(PointSet xOrder, PointSet yOrder, int left, int right){

		//System.out.print("XOrder:" + xOrder.toString());
		//System.out.print("YOrder size is:" + yOrder.list.size() + yOrder.toString());

		System.out.println("Right is: " + right + "Left is:" + left);
		Point[] closestPair = new Point[2];

		if(yOrder.list.size() <= 3){
			System.out.print("USED BRUTE FORCE");
			//then do brute force by comparing them
			return closestPointBF();

		//set is larger than 3, using divide and conquer

			System.out.println("IN ELSE!");
			int imaginaryLine = yOrder.list.size()/2;//separating X logically

			//PointPair closestSoFar;//closest pair found so far
			double distanceBetweenClosest = Integer.MAX_VALUE;

			//physically splitting up y
			PointSet yLeft= new PointSet();
			PointSet yRight = new PointSet();

			for(int i =0; i <imaginaryLine; i ++ )

			for(int j = imaginaryLine; j < yOrder.list.size(); j++)

			//make two recursive calls
			PointPairSet leftRecursive = closestPoints(xOrder, yLeft, 0, imaginaryLine);//left side examined
			PointPairSet rightRecursive = closestPoints(xOrder, yRight, imaginaryLine, right);//right side examined

			double closestLeft = Integer.MAX_VALUE;
			double closestRight = Integer.MAX_VALUE;

			for(int k = 0; k <leftRecursive.numElements(); k++){

				if(leftRecursive.get(k).distance() < closestLeft)
					closestLeft = leftRecursive.get(k).distance();

			for(int k = 0; k <rightRecursive.numElements(); k++){

				if(rightRecursive.get(k).distance() < closestRight)
					closestRight = rightRecursive.get(k).distance();

			for(int i =0; i < yOrder.list.size(); i++){

				//if outside range delete
				if(yOrder.list.get(i).getX()<left || yOrder.list.get(i).getX() > right){
					//discard all points from ylist that are not in the strip
					System.out.print("Removed from y:" + yOrder.list.get(i));

			//These points are now examined in linear time to determine the closest pair
			return closestPointBF();

//	type == 0 implies X
	public void qsort(int type){

		if(type == 0)
			compareMethod = new XComparator();
			compareMethod = new YComparator();


//	sorts list of Points
	private void quickSort(int from, int to){

		if(from >= to)

		int pivot = (from + to)/ 2;

		int i = from;
		int j = to;

		while(i <= j){
			if(compareMethod.compare(list.get(i), list.get(pivot)) < 1)
			else if( compareMethod.compare(list.get(j),list.get(pivot)) > -1)

				Point temp = list.set(i, list.get(j));
				list.set(j, temp);

		if( pivot < j){
			Point temp = list.set(j, list.get(pivot));
			list.set(pivot, temp);
			pivot = j;
		else if(pivot > i){
			Point temp = list.set(i, list.get(pivot));
			list.set(pivot, temp);
			pivot = i;

		quickSort(from, pivot-1);


	public static void main(String[] args){

		PointSet set = new PointSet();

		set.add(new Point(2, 1));
		set.add(new Point(3, 2));
		set.add(new Point(4, 3));
		set.add(new Point(5, 4));
		set.add(new Point(6, 5));
		/*set.add(new Point(5, 5));
		set.add(new Point(3, 3));
		set.add(new Point(3, 2));
		set.add(new Point(4, 1));*/

		//PointPairSet t = new PointPairSet();
		//t.add(new PointPair(new Point(1, 1), new Point(3, 55)));

		PointPairSet returned = set.closestPointsDC();

		//	PointSet tester = set.closestPointBF();

5 Years
Discussion Span
Last Post by sariberri

According to Wikipedia:

The problem can be solved in O(n log n) time using the recursive divide and conquer approach, e.g., as follows[1]:
1. Sort points along the x-coordinate (I did this)
2. Split the set of points into two equal-sized subsets by a vertical line x = xmid (I did this)
3. Solve the problem recursively in the left and right subsets. This will give the left-side and right-side minimal distances dLmin and dRmin respectively.
5. Find the minimal distance dLRmin among the pair of points in which one point lies on the left of the dividing vertical and the second point lies to the right.
6. The final answer is the minimum among dLmin, dRmin, and dLRmin.

I'm stuck on step 3. I don't get how I'm supposed to get the left-side and right-side minimal distances and then compare them without wasting a lot of runtime....:/

This topic has been dead for over six months. Start a new discussion instead.
Have something to contribute to this discussion? Please be thoughtful, detailed and courteous, and be sure to adhere to our posting rules.