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.
Naive Approach: The basic way to solve the problem is as follows:
Calculate the distance of all pairs of points and output the minimum distance among them.
Time complexity: O(N2), where N is the number of points.
Auxiliary Space: O(1)
Efficient Approach: To solve the problem follow the below idea:
Sweep Line Algorithm:The idea is to represent an instance of the problem as a set of events that correspond to points in the plane. The events are processed in increasing order according to their x or y coordinates. Using a vertical line, horizontal line or radial line that is conceptually “swept” across the plane.
Minimum distance d
Follow the steps mentioned below to implement the idea:
- Sort the given set of points in ascending order of their x-coordinate.
- We go through the points by taking a vertical line swept from left to right and maintain a value d: the minimum distance between two points seen so far.
- At each point, we find the nearest point to the left. If the distance is less than d, it is the new minimum distance and we update the value of d.
- If the current point is (x, y) and there is a point to the left within a distance of less than d,
- the x coordinate of such a point must be between [x ? d, x] and the y coordinate must be between [y? d, y+ d].
- Thus, it suffices to only consider points that are located in those ranges. We can achieve this search in O(logN) time by using set st.
- The efficiency of the algorithm is based on the fact that the region always contains only O(1) points.
- Return distance d as a final result.
Below is the implementation of the above approach:
C++
#include <bits/stdc++.h>using namespace std;// To find the closest pair of pointslong closestPair(vector<pair<int, int> > coordinates, int n){ int i; // Vector pair to store points on plane vector<pair<int, int> > v; for (i = 0; i < n; i++) v.push_back({ coordinates[i].first, coordinates[i].second }); // Sort them according to their // x-coordinates sort(v.begin(), v.end()); // Minimum distance b/w points // seen so far long d = INT_MAX; // Keeping the points in // increasing order set<pair<int, int> > st; st.insert({ v[0].first, v[0].second }); for (i = 1; i < n; i++) { auto l = st.lower_bound( { v[i].first - d, v[i].second - d }); auto r = st.upper_bound( { v[i].first, v[i].second + d }); if (l == st.end()) continue; for (auto p = l; p != r; p++) { pair<int, int> val = *p; long dis = (v[i].first - val.first) * (v[i].first - val.first) + (v[i].second - val.second) * (v[i].second - val.second); // Updating the minimum // distance dis if (d > dis) d = dis; } st.insert({ v[i].first, v[i].second }); } return d;}// Driver codeint main(){ // Points on a plane P[i] = {x, y} vector<pair<int, int> > 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;} |
Java
// Java code implementation:import java.io.*;import java.util.*;class GFG { // To find the closest pair of points public static long closestPair(int[][] coordinates, int n) { // List of pairs to store points on plane List<int[]> points = new ArrayList<>(); for (int i = 0; i < n; i++) { points.add(new int[] { coordinates[i][0], coordinates[i][1] }); } // Sort them according to their x-coordinates Collections.sort(points, new Comparator<int[]>() { public int compare(int[] a, int[] b) { return a[0] - b[0]; } }); // Minimum distance b/w points seen so far long d = (long)Math.pow(10, 18); // Keeping the points in increasing order Set<int[]> st = new HashSet<>(); st.add(points.get(0)); for (int i = 1; i < n; i++) { Set<int[]> l = new HashSet<>(); for (int[] p : st) { if (p[0] >= points.get(i)[0] - d && p[1] >= points.get(i)[1] - d) { l.add(p); } } Set<int[]> r = new HashSet<>(); for (int[] p : st) { if (p[0] <= points.get(i)[0] + d && p[1] <= points.get(i)[1] + d) { r.add(p); } } Set<int[]> intersection = new HashSet<>(l); intersection.retainAll(r); if (intersection.size() == 0) { continue; } for (int[] val : intersection) { long dis = (long)Math.pow( points.get(i)[0] - val[0], 2) + (long)Math.pow( points.get(i)[1] - val[1], 2); // Updating the minimum distance dis if (d > dis) { d = dis; } } st.add(points.get(i)); } return d; } public static void main(String[] args) { // Points on a plane P[i] = (x, y) int[][] P = { { 1, 2 }, { 2, 3 }, { 3, 4 }, { 5, 6 }, { 2, 1 } }; int n = P.length; // Function call System.out.println("The smallest distance is " + closestPair(P, n)); }}// This code is contributed by sankar. |
Python3
import sysimport math# To find the closest pair of pointsdef closestPair(coordinates, n): # List of pairs to store points on plane points = [(coordinates[i][0], coordinates[i][1]) for i in range(n)] # Sort them according to their x-coordinates points.sort() # Minimum distance b/w points seen so far d = sys.maxsize # Keeping the points in increasing order st = set() st.add(points[0]) for i in range(1, n): l = set([p for p in st if p[0] >= points[i][0]-d and p[1] >= points[i][1]-d]) r = set([p for p in st if p[0] <= points[i][0]+d and p[1] <= points[i][1]+d]) intersection = l & r if len(intersection) == 0: continue for val in intersection: dis = math.pow(points[i][0] - val[0], 2) + math.pow(points[i][1] - val[1], 2) # Updating the minimum distance dis if d > dis: d = dis st.add(points[i]) return d# Points on a plane P[i] = (x, y)P = [(1, 2), (2, 3), (3, 4), (5, 6), (2, 1)]n = len(P)# Function callprint("The smallest distance is", closestPair(P, n))# This code is contributed by lokeshpotta20. |
C#
// C# code implementationusing System;using System.Collections;using System.Collections.Generic;using System.Linq;public class GFG{ // To find the closest pair of points public static long closestPair(int[][] coordinates, int n) { // List of pairs to store points on plane List<int[]> points = new List<int[]>(); for (int i = 0; i < n; i++) { points.Add(new int[] { coordinates[i][0], coordinates[i][1] }); } // Sort them according to their x-coordinates points.Sort(Compare); // Minimum distance b/w points seen so far long d = (long)Math.Pow(10, 18); // Keeping the points in increasing order HashSet<int[]> st = new HashSet<int[]>(); st.Add(points.First()); foreach (int[] point in points.Skip(1)) { HashSet<int[]> l = new HashSet<int[]>(); foreach (int[] p in st) { if (p[0] >= point[0] - d && p[1] >= point[1] - d) { l.Add(p); } } HashSet<int[]> r = new HashSet<int[]>(); foreach (int[] p in st) { if (p[0] <= point[0] + d && p[1] <= point[1] + d) { r.Add(p); } } HashSet<int[]> intersection = new HashSet<int[]>(l); intersection.IntersectWith(r); if (intersection.Count == 0) { continue; } foreach (int[] val in intersection) { long dis = (long)Math.Pow( point[0] - val[0], 2) + (long)Math.Pow( point[1] - val[1], 2); // Updating the minimum distance dis if (d > dis) { d = dis; } } st.Add(point); } return d; } // Compare function for sorting public static int Compare(int[] a, int[] b) { return a[0] - b[0]; } public static void Main(String[] args) { // Points on a plane P[i] = (x, y) int[][] P = { new int[] { 1, 2 }, new int[] { 2, 3 }, new int[] { 3, 4 }, new int[] { 5, 6 }, new int[] { 2, 1 } }; int n = P.Length; // Function call Console.WriteLine("The smallest distance is " + closestPair(P, n)); }} |
Javascript
// To find the closest pair of pointsfunction closestPair(coordinates, n) { // List of pairs to store points on plane var points = []; for (var i = 0; i < n; i++) { points.push([coordinates[i][0], coordinates[i][1]]); } // Sort them according to their x-coordinates points.sort(function(a, b) { return a[0] - b[0]; }); // Minimum distance b/w points seen so far var d = Number.MAX_SAFE_INTEGER; // Keeping the points in increasing order var st = new Set(); st.add(points[0]); for (var i = 1; i < n; i++) { var l = new Set(); st.forEach(function(p) { if (p[0] >= points[i][0]-d && p[1] >= points[i][1]-d) { l.add(p); } }); var r = new Set(); st.forEach(function(p) { if (p[0] <= points[i][0]+d && p[1] <= points[i][1]+d) { r.add(p); } }); var intersection = new Set([...l].filter(x => r.has(x))); if (intersection.size == 0) { continue; } intersection.forEach(function(val) { var dis = Math.pow(points[i][0] - val[0], 2) + Math.pow(points[i][1] - val[1], 2); // Updating the minimum distance dis if (d > dis) { d = dis; } }); st.add(points[i]); } return d;}// Points on a plane P[i] = (x, y)var P = [[1, 2], [2, 3], [3, 4], [5, 6], [2, 1]];var n = P.length;// Function callconsole.log("The smallest distance is", closestPair(P, n));// This code is contributed by Prasad Kandekar(prasad264) |
Output
The smallest distance is 2
Time Complexity: O(N * log(N))
Auxiliary Space: O(N)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
