Closest Pair of Points using Sweep Line Algorithm

Given an array of N points in the plane, the task is to find a pair of points with the smallest distance between them, where the distance between two points (x1, y1) and (x2, y2) can be calculated as [(x1 - x2) ^ 2] + [(y1 - y2) ^ 2].

Examples:

Input: P[] = { {1, 2}, {2, 3}, {3, 4}, {5, 6}, {2, 1} }
Output: The smallest distance is 2.
Explanation: Distance between points as:
P[0] and P[1] = 2, P[0] and P[2] = 8, P[0] and P[3] = 32, P[0] and P[4] = 2
P[1] and P[2] = 2, P[1] and P[3] = 18, P[1] and P[4] = 4
P[2] and P[3] = 8, P[2] and P[4] = 10
P[3] and P[4] = 34
Minimum distance among them all is 2.

Input: P[] = { {0, 0}, {2, 1}, {1, 1} }
Output: The smallest distance is 1.

Approach: To solve the problem follow the below idea:

The idea is to use Sweep Line Algorithm to find the smallest distance between a pair of points. We can sort the points on the basis of their x-coordinates and start iterating over all the points in increasing order of their x-coordinates.

Suppose we are at the Kth point so all the points to the left of Kth point will be already processed. Let the minimum distance between 2 points found so far be D. So, to process the Kth point, we will consider only those points whose distance from Kth point < D. Maintain a set to store the previously processed points whose x-coordinates are less than D distance from Kth point. All the points in the set are ordered by their y-coordinates. In the below image, the light-green shaded region represents all the points which are available in the set.

Now to search for the points in the set which are less than D distance away from point K, we will consider only those points whose y-coordinates are less than D distance from Kth point (points having their y-coordinates in range (Y_K - D, Y_K + D)). This can be performed in O(logN) time using Binary Search on set. Iterate over all those points and if distance is less than D, then update the minimum distance. In the above image, the dark-green region represents all the points in the set whose y-coordinates are less than D distance from Kth point. The efficiency of the algorithm is based on the fact that this region will contain O(1) points on an average.

After iterating over all the points, return the smallest distance found between any 2 points.

Below is the implementation of the above approach:

#include <bits/stdc++.h> using namespace std; // To find the closest pair of points long long closestPair(vector<pair<long long, long long> > coordinates,  int n) {  // Sort points according to x-coordinates  sort(coordinates.begin(), coordinates.end());  // Set to store already processed points whose distance  // from the current points is less than the smaller  // distance so far  set<pair<long long, long long> > s;  long long squaredDistance = LLONG_MAX;  long long j = 0;  for (long long i = 0; i < n; ++i) {  // Find the value of D  long long D = ceil(sqrt(squaredDistance));  while (coordinates[i].first - coordinates[j].first >= D) {  s.erase({ coordinates[j].second, coordinates[j].first });  j += 1;  }   // Find the first point in the set whose y-coordinate is less than D distance from ith point   auto start  = s.lower_bound({ coordinates[i].second - D,  coordinates[i].first });  // Find the last point in the set whose y-coordinate is less than D distance from ith point   auto end  = s.upper_bound({ coordinates[i].second + D,  coordinates[i].first });  // Iterate over all such points and update the minimum distance  for (auto it = start; it != end; ++it) {  long long dx = coordinates[i].first - it->second;  long long dy = coordinates[i].second - it->first;  squaredDistance = min(squaredDistance, 1LL * dx * dx + 1LL * dy * dy);  }    // Insert the point as {y-coordinate, x-coordinate}  s.insert({ coordinates[i].second,  coordinates[i].first });  }  return squaredDistance; } // Driver code int main() {  // Points on a plane P[i] = {x, y}  vector<pair<long long, long long> > P = {  { 1, 2 }, { 2, 3 }, { 3, 4 }, { 5, 6 }, { 2, 1 }  };  int n = P.size();  // Function call  cout << "The smallest distance is "  << closestPair(P, n);  return 0; } 

import java.util.*; public class ClosestPair {  // To find the closest pair of points  public static long closestPair(List<long[]> coordinates, int n) {  // Sort points according to x-coordinates  Collections.sort(coordinates, Comparator.comparingLong(a -> a[0]));  // TreeSet to store already processed points whose distance  // from the current points is less than the smallest distance so far  TreeSet<long[]> set = new TreeSet<>(Comparator.comparingLong(a -> a[1]));  long squaredDistance = Long.MAX_VALUE;  int j = 0;  for (int i = 0; i < n; ++i) {  // Find the value of D  long D = (long) Math.ceil(Math.sqrt(squaredDistance));  while (coordinates.get(i)[0] - coordinates.get(j)[0] >= D) {  set.remove(new long[]{coordinates.get(j)[1], coordinates.get(j)[0]});  j += 1;  }  // Find the first point in the set whose y-coordinate is less than D distance from ith point  long[] lowerBound = new long[]{coordinates.get(i)[1] - D, Long.MIN_VALUE};  // Find the last point in the set whose y-coordinate is less than D distance from ith point  long[] upperBound = new long[]{coordinates.get(i)[1] + D, Long.MAX_VALUE};  // Iterate over all such points and update the minimum distance  for (long[] point : set.subSet(lowerBound, upperBound)) {  long dx = coordinates.get(i)[0] - point[1];  long dy = coordinates.get(i)[1] - point[0];  squaredDistance = Math.min(squaredDistance, dx * dx + dy * dy);  }  // Insert the point as {y-coordinate, x-coordinate}  set.add(new long[]{coordinates.get(i)[1], coordinates.get(i)[0]});  }  return squaredDistance;  }  public static void main(String[] args) {  // Points on a plane P[i] = {x, y}  List<long[]> P = new ArrayList<>();  P.add(new long[]{1, 2});  P.add(new long[]{2, 3});  P.add(new long[]{3, 4});  P.add(new long[]{5, 6});  P.add(new long[]{2, 1});  int n = P.size();  // Function call  System.out.println("The smallest distance is " + closestPair(P, n));  } } 

import math from sortedcontainers import SortedSet # Point class for 2-D points class Point: def __init__(self, x, y) : self.x = x self.y = y def closestPair(coordinates, n) : # Sort points according to x-coordinates coordinates.sort(key=lambda p: p.x) # SortedSet to store already processed points whose distance # from the current points is less than the smaller distance so far s = SortedSet(key=lambda p: (p.y, p.x)) squaredDistance = 1e18 j = 0 for i in range(len(coordinates)): # Find the value of D D = math.ceil(math.sqrt(squaredDistance)) while j <= i and coordinates[i].x - coordinates[j].x >= D: s.discard(Point(coordinates[j].x, coordinates[j].y)) j += 1 # Find the first point in the set whose y-coordinate is less than D distance from ith point start = Point(coordinates[i].x, coordinates[i].y - D) # Find the last point in the set whose y-coordinate is less than D distance from ith point end = Point(coordinates[i].x, coordinates[i].y + D) # Iterate over all such points and update the minimum distance for it in s.irange(start, end): dx = coordinates[i].x - it.x dy = coordinates[i].y - it.y squaredDistance = min(squaredDistance, dx * dx + dy * dy) # Insert the point into the SortedSet s.add(Point(coordinates[i].x, coordinates[i].y)) return squaredDistance # Driver code if __name__ == "__main__": # Points on a plane P[i] = {x, y} P = [ Point(1, 2), Point(2, 3), Point(3, 4), Point(5, 6), Point(2, 1) ] n = 5 # Function call print("The smallest distance is", closestPair(P, n)) 

// To find the closest pair of points function closestPair(coordinates) {  // Sort points according to x-coordinates  coordinates.sort((a, b) => a[0] - b[0]);  // Array to store already processed points  let s = [];  let squaredDistance = Number.MAX_SAFE_INTEGER;  let j = 0;  for (let i = 0; i < coordinates.length; ++i) {  // Find the value of D  let D = Math.ceil(Math.sqrt(squaredDistance));    // Remove points from the set that are too far from the current point  while (coordinates[i][0] - coordinates[j][0] >= D) {  s.shift();  j += 1;  }  // Find points within the range [coordinates[i][1] - D, coordinates[i][1] + D]  let start = coordinates[i][1] - D;  let end = coordinates[i][1] + D;  // Iterate over all such points and update the minimum distance  for (let k = 0; k < s.length; ++k) {  let dx = coordinates[i][0] - s[k][1];  let dy = coordinates[i][1] - s[k][0];  squaredDistance = Math.min(squaredDistance, dx * dx + dy * dy);  }  // Insert the point into the set  s.push([coordinates[i][1], coordinates[i][0]]);  }  return squaredDistance; } // Driver code function main() {  // Points on a plane P[i] = [x, y]  let P = [  [1, 2],  [2, 3],  [3, 4],  [5, 6],  [2, 1]  ];    // Function call  console.log("The smallest distance is", closestPair(P)); } // Call main function main(); 

The smallest distance is 2 

Time Complexity: O(N * logN), because we iterate over all the N points and logN for binary search to find the points whose Y coordinates are less than D distance away from the current point where D is the minimum distance between any two points covered so far.
Auxiliary Space: O(N)