Closest Pair of Points | O(nlogn) Implementation | GeeksforGeeks

Closest Pair of Points
Closest Pair of Points | O(nlogn) Implementation | GeeksforGeeks
We are given an array of n points in the plane, and the problem is to find out the closest pair of points in the array.


O(nLogn). The idea is to presort all points according to y coordinates. Let the sorted array be Py[]. When we make recursive calls, we need to divide points of Py[] also according to the vertical line. We can do that by simply processing every point and comparing its x coordinate with x coordinate of middle line.

Time Complexity:Let Time complexity of above algorithm be T(n). Let us assume that we use a O(nLogn) sorting algorithm. The above algorithm divides all points in two sets and recursively calls for two sets. After dividing, it finds the strip in O(n) time. Also, it takes O(n) time to divide the Py array around the mid vertical line. Finally finds the closest points in strip in O(n) time. So T(n) can expressed as follows
T(n) = 2T(n/2) + O(n) + O(n) + O(n)
T(n) = 2T(n/2) + O(n)
T(n) = T(nLogn)

// A utility function to find the distance beween the closest points of

// strip of given size. All points in strip[] are sorted accordint to

// y coordinate. They all have an upper bound on minimum distance as d.

// Note that this method seems to be a O(n^2) method, but it's a O(n)

// method as the inner loop runs at most 6 times

float stripClosest(Point strip[], int size, float d)

{

    float min = d;  // Initialize the minimum distance as d

    // Pick all points one by one and try the next points till the difference

    // between y coordinates is smaller than d.

    // This is a proven fact that this loop runs at most 6 times

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

        for (int j = i+1; j < size && (strip[j].y - strip[i].y) < min; ++j)

            if (dist(strip[i],strip[j]) < min)

                min = dist(strip[i], strip[j]);

    return min;

}

// A recursive function to find the smallest distance. The array Px contains

// all points sorted according to x coordinates and Py contains all points

// sorted according to y coordinates

float closestUtil(Point Px[], Point Py[], int n)

{

    // If there are 2 or 3 points, then use brute force

    if (n <= 3)

        return bruteForce(Px, n);

    // Find the middle point

    int mid = n/2;

    Point midPoint = Px[mid];

    // Divide points in y sorted array around the vertical line.

    // Assumption: All x coordinates are distinct.

    Point Pyl[mid+1];   // y sorted points on left of vertical line

    Point Pyr[n-mid-1];  // y sorted points on right of vertical line

    int li = 0, ri = 0;  // indexes of left and right subarrays

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

    {

      if (Py[i].x <= midPoint.x)

         Pyl[li++] = Py[i];

      else

         Pyr[ri++] = Py[i];

    }

    // Consider the vertical line passing through the middle point

    // calculate the smallest distance dl on left of middle point and

    // dr on right side

    float dl = closestUtil(Px, Pyl, mid);

    float dr = closestUtil(Px + mid, Pyr, n-mid);

    // Find the smaller of two distances

    float d = min(dl, dr);

    // Build an array strip[] that contains points close (closer than d)

    // to the line passing through the middle point

    Point strip[n];

    int j = 0;

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

        if (abs(Py[i].x - midPoint.x) < d)

            strip[j] = Py[i], j++;

    // Find the closest points in strip.  Return the minimum of d and closest

    // distance is strip[]

    return min(d, stripClosest(strip, j, d) );

}

// The main functin that finds the smallest distance

// This method mainly uses closestUtil()

float closest(Point P[], int n)

{

    Point Px[n];

    Point Py[n];

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

    {

        Px[i] = P[i];

        Py[i] = P[i];

    }

    qsort(Px, n, sizeof(Point), compareX);

    qsort(Py, n, sizeof(Point), compareY);

    // Use recursive function closestUtil() to find the smallest distance

    return closestUtil(Px, Py, n);

}

More Reference:

https://www.topcoder.com/community/competitive-programming/tutorials/line-sweep-algorithms/

Given a set of points, find the pair that is closest (with either metric). Of course, this can be solved in O(N2) time by considering all the pairs, but a line sweep can reduce this to O(N log N).

Suppose that we have processed points 1 to N - 1 (ordered by X) and the shortest distance we have found so far is h. We now process point N and try to find a point closer to it than h. We maintain a set of all already-processed points whose X coordinates are within h of point N, as shown in the light grey rectangle. As each point is processed, it is added to the set, and when we move on to the next point or when h is decreased, points are removed from the set. The set is ordered by y coordinate. A balanced binary tree is suitable for this, and accounts for the log N factor.

To search for points closer than h to point N, we need only consider points in the active set, and furthermore we need only consider points whose y coordinates are in the range yN - h to yN + h (those in the dark grey rectangle). This range can be extracted from the sorted set in O(log N) time, but more importantly the number of elements is O(1) (the exact maximum will depend on the metric used), because the separation between any two points in the set is at least h. It follows that the search for each point requires O(log N) time, giving a total of O(N log N).

http://www.cs.ucsb.edu/~suri/cs235/ClosestPair.pdf

Consider a point p ∈ S1. All points of S2 within distance δ of p must lie in a δ × 2δ rectangle R.

How many points can be inside R if each pair is at least δ apart?

• In 2D, this number is at most 6!

• So, we only need to perform 6 × n/2 distance comparisons!

Pick out points whose projection is within δ of p; at most six.

• We can do this for all p, by walking sorted lists of P1 and P2, in total O(n) time.

• The sorted lists for P1, P2 can be obtained from pre-sorting of S1, S2.

• Final recurrence is T(n) = 2T(n/2) + O(n), which solves to T(n) = O(n log n).

http://massivealgorithms.blogspot.com/2014/07/closest-pair-of-points-onlogn.html

http://noalgo.info/793.html

//寻找下标在[st, ed]之间的最近点对
double closestPair(int st, int ed, int &p1, int &p2)
{
 double dis = oo, temdis;
 if (st >= ed) return dis;

 int mid = st + ((ed - st) >> 1), t1, t2;
 if ((temdis = closestPair(st, mid, t1, t2)) < dis)  //左边
  dis = temdis, p1 = t2, p2 = t2;
 if ((temdis = closestPair(mid+1, ed, t1, t2)) < dis)//右边
  dis = temdis, p1 = t1, p2 = t2;

 //寻找距离中间x坐标小于dis的点，并按Y坐标排序
 int len = 0;
 for (int i = st; i <= ed; i++)
  if (fabs(v[i].x - v[mid].x) < dis)
   tem[len++] = v[i];
 sort(tem, tem + len, cmpByY);

 //考虑每个点附近至多8个点，由距离控制
 for (int i = 0; i < len; i++)
  for (int j = i + 1; j < len && tem[j].y - tem[i].y <= dis; j++)
   if ((temdis = calDis(tem[i], tem[j])) < dis)
    dis = temdis, p1 = i, p2 = j;
 return dis;
}

int main()
{
 //输入n个点，并按X坐标排序
 int n; scanf("%d", &n);
 for (int i = 0; i < n; i++) scanf("%lf%lf", &v[i].x, &v[i].y);
 sort(v, v + n, cmpByX); 

 int p1, p2;
 double dis = closestPair(0, n - 1, p1, p2);
 printf("Cloest Pair：(%lf,%lf)-(%lf,%lf) %.2lf\n", v[p1].x, v[p1].y, v[p2].x, v[p2].y, dis/2);
}

Read full article from Closest Pair of Points | O(nlogn) Implementation | GeeksforGeeks