Problem Statement

1Problem Description : Given n points in the plane, find smallest euclidean distance between them. 
2
3NOTE: 
41) Points are given by their x and y coordinates.
52) Euclidean distance between two points p1 = (x1, y1) and p2 = (x2, y2) is expressed as d(A, B) = √( (x1-x2)² + (y1-y2)² )
6
7Constraints: n > 2
8
9Input: 
10  Array of x coordinate values of size n
11  Array of y coordinate values of size n
12
13Output: Smallest distance.
14

1Example 1 :
2
3Input : 
4    int[] x = {2, 5, 12};
5    int[] y = {3, 1, 30};
6
7Output: 3.605551275463989
8
9Explanation :
10    Distance between (2, 3) and  (5, 1) is 3.605551275463989
11    Distance between (2, 3) and  (12, 30) is 28.792360097775937
12    Distance between (5, 1) and  (12, 30) is 29.832867780352597
13
14    So shortest distance is 3.605551275463989

1Example 2 :
2
3  Input : 
4    int[] x = {2, 12, 40, 5, 12, 3};
5    int[] y = {3, 30, 50, 1, 10, 4};
6
7  Output: 1.4142135623730951
8
9  Explanation :
10    Distance between (2, 3) and  (12, 30) is 28.792360097775937
11    Distance between (2, 3) and  (40, 50) is 60.440052945046304
12    Distance between (2, 3) and  (5, 1) is 3.605551275463989
13    Distance between (2, 3) and  (12, 10) is 12.206555615733702
14    Distance between (2, 3) and  (3, 4) is 1.4142135623730951
15    Distance between (12, 30) and  (40, 50) is 34.40930106817051
16    Distance between (12, 30) and  (5, 1) is 29.832867780352597
17    Distance between (12, 30) and  (12, 10) is 20.0
18    Distance between (12, 30) and  (3, 4) is 27.51363298439521
19    Distance between (40, 50) and  (5, 1) is 60.21627686929839
20    Distance between (40, 50) and  (12, 10) is 48.82622246293481
21    Distance between (40, 50) and  (3, 4) is 59.033888572581766
22    Distance between (5, 1) and  (12, 10) is 11.40175425099138
23    Distance between (5, 1) and  (3, 4) is 3.605551275463989
24    Distance between (12, 10) and  (3, 4) is 10.816653826391969
25    So shortest distance is 1.4142135623730951

Solution Approach

Naïve Solution

Code Implementation

1import java.util.Arrays;
2
3public class ClosetPairDistanceBruteForce {
4
5    public static class Point {
6        int x;
7        int y;
8
9        Point(int x, int y) {
10            this.x = x;
11            this.y = y;
12        }
13
14        @Override
15        public String toString(){
16            return "("+x+", "+y+")";
17        }
18    }
19
20    public Point[] closestPair(Point[] points, int n) {
21        Point[] result = new Point[2];
22        double min = Double.MAX_VALUE;
23
24        for (int i = 0; i < n; i++) {
25            for (int j = i + 1; j < n; j++) {
26                double dist = distance(points[i], points[j]);
27                if(dist < min) {
28                    min = dist;
29                    result[0] = points[i];
30                    result[1] = points[j];
31                }
32                min = min(min, dist);
33            }
34        }
35        return result;
36    }
37
38    // Method to find distance between two points p1 nd p2
39    private double distance(Point p1, Point p2){
40        return Math.sqrt((p1.x-p2.x) * (p1.x-p2.x) + (p1.y-p2.y) * (p1.y-p2.y)) ;
41    }
42
43    // Method to find min value among two values
44    private double min(double val1, double val2) {
45        return Math.min(val1, val2);
46    }
47
48    public static void main(String[] args) {
49        int[] x = {2, 12, 40, 5, 12, 3};
50        int[] y = {3, 30, 50, 1, 10, 4};
51
52        int n = x.length;
53
54        Point[] points = new Point[n] ;
55
56        for(int i=0; i<n; i++) {
57            points[i] = new Point(x[i], y[i]);
58        }
59        ClosetPairDistanceBruteForce obj = new ClosetPairDistanceBruteForce();
60        Point[] closestPair = obj.closestPair(points, n);
61        Point p1 = closestPair[0];
62        Point p2 = closestPair[1];
63        System.out.println("Closest Pair is : "+ Arrays.toString(closestPair));
64    }
65
66}

Using Divide And Conquer

Prerequisite

• Divide And Conquer Approach

Algorithm

1Input : Array of points represented using x and y coordinates
2
3Step1: Create array px which is sorted array of original array by x coordinate.
4       Create a sorted array py which is sorted array of original array by y coordinate.
5       Initialize low to 0 and high to n-1 (where n is length of the array)
6
7Step 1: Find middle point of the px using (low+high)/2
8
9Step 2: Divide px array into two halves, The first sub array contains from px[low] to px[mid] and second array contains from px[mid+1] to p[high]
10
11Step 3: Recursively compute smallest distance from both left and right sub arrays leftMin and rightMin and then compute minimum of LeftMin and right which is called min.
12
13Step 4: Create a strip of coordinates from py array whose distance is less than min, and compute minValue from strip of coordinates which is called minFromStrip
14
15Step 5: Finally the minimum is minimum of leftMin, rightMin and minFromStrip
16
17Output : Pair of points which are closer in the plane

Code Implementation

1import java.util.Arrays;
2public class ClosetPairDistance {
3
4    // point class
5    private static class Point {
6        int x;
7        int y;
8
9        Point(int x, int y) {
10            this.x = x;
11            this.y = y;
12        }
13    }
14
15    private static double MIN_VAL = Double.MAX_VALUE;
16
17    // Method to find the min distance
18    public double closestPair(Point[] points){
19        int n = points.length;
20        Point[] xSorted = new Point[n];
21        Point[] ySorted = new Point[n];
22
23        for(int i=0; i<n; i++){
24            xSorted[i] = points[i];
25            ySorted[i] = points[i];
26        }
27        // sort array using x coordinate
28        Arrays.sort(xSorted, (p1, p2) -> p1.x - p2.x);
29
30        // sort array using y coordinate
31        Arrays.sort(ySorted, (p1, p2) -> p1.y - p2.y);
32
33        return closestPair(xSorted, ySorted, 0, n-1);
34    }
35
36
37    // recursive call to find the closest pair distance
38    private double closestPair(Point[] px, Point[] py, int low, int high) {
39        // count points in the search space
40        int n = high - low + 1;
41
42        //If there are 2 or 3 points, then use brute force
43        if (n <= 3) {
44            return closestPairUsingBruteForce(px);
45        }
46
47        // find middle element of the search space
48        // to divide the space into two halves
49        int mid = low + (high - low)/2 ;
50        Point midPoint = px[mid];
51
52        // find left and right min recursively
53        double leftMin = closestPair(px, py, low, mid);
54        double rightMin = closestPair(px, py, mid+1, high);
55
56        // find the min distance from left and right search space
57        double minDistance = Math.min(leftMin, rightMin);
58
59        // there might be possibility that min distance might be there by one point from left and one point from right
60        // to find such scenarios create strip of distance minDistance from both sides
61        // find the strip of values which are closer at a distance of d
62        int stripLeft = -1;
63        int stripRight = -1;
64
65        for(int i=low; i<high; i++) {
66            if( Math.abs(py[i].x - midPoint.x) < minDistance ) {
67                if(stripLeft == -1) {
68                    stripLeft = i;
69                }else {
70                    stripRight = i;
71                }
72            }
73        }
74        // now find the min distance from strip of points
75        double minFromStrip = getMinStripeDistance(py, stripLeft, stripRight);
76        // finally min distance id the one min of left, right and from the strip
77        return min(minDistance, minFromStrip);
78    }
79
80
81    // brute force method to check min distance
82    // this method is used only if we have <=3 points in the plane
83    public double closestPairUsingBruteForce(Point[] points) {
84        double min = MIN_VAL;
85
86        for (int i = 0; i < points.length; i++) {
87            for (int j = i + 1; j < points.length; j++) {
88                double dist = distance(points[i], points[j]);
89                if(dist < min) {
90                    min = dist;
91                }
92                min = min(min, dist);
93            }
94        }
95        return min;
96    }
97
98    // min distance in strip of points
99    private double getMinStripeDistance(Point[] ySorted, int low, int high) {
100        double min = MIN_VAL ;
101
102        //Pick all points one by one and try the next points till the difference
103        //between y coordinates is smaller than d.
104        //This is a proven fact that this loop runs at most 6 times
105        for(int i=low; i<=high; i++) {
106            for(int j=i+1; j<=high; j++) {
107                min = min(min, distance(ySorted[i], ySorted[j]));
108            }
109        }
110        return min;
111    }
112
113    // Method to find distance between two points p1 nd p2
114    private double distance(Point p1, Point p2){
115        return Math.sqrt((p1.x-p2.x) * (p1.x-p2.x) + (p1.y-p2.y) * (p1.y-p2.y)) ;
116    }
117
118    // method to find min between two values
119    private double min(double val1, double val2) {
120        return Math.min(val1, val2);
121    }
122
123    // driver method
124    public static void main(String[] args) {
125        int[] x = {2, 12, 40, 5, 12, 3};
126        int[] y = {3, 30, 50, 1, 10, 4};
127
128        int n = x.length;
129        Point[] points = new Point[n] ;
130
131        for(int i=0; i<n; i++) {
132            points[i] = new Point(x[i], y[i]);
133        }
134
135        ClosetPairDistance obj = new ClosetPairDistance();
136        double distance = obj.closestPair(points);
137
138        System.out.println(distance);
139    }
140
141}

Complexity Analysis

• Time Complexity : O(n log(n))
• Space Complexity : O(n)