closest pair algorithm that runs in O(nlogn) time. However, that algorithm can b

Question

closest pair algorithm that runs in O(nlogn) time. However, that algorithm can be improved further when additional assumption is made. Here is one. Suppose that there are n^2 bugs sitting on a piece of paper of size n by n. Any two bugs must stay away by at least 1. Each bug is given as a pair of coordinates. Design a linear-time algorithm that nds the closest pair of bugs. (Hint: since the input size is n^2, the linear time here really means the running time is O(n^2) where the n^2 is the number of bugs.)

Explanation / Answer

=>The Brute force solution is O(n^2), compute the distance between each pair and return the smallest.

Algorithm
Input: An array of bugs
Output: The smallest distance between two bugs in the given array.
As a pre-processing step, input array is sorted according to x coordinates.
a) Find the middle point in the sorted array, we can take P[n/2] as middle point.
b) Divide the given array in two halves. The first subarray contains bugs from P[0] to P[n/2]. The second subarray contains bugs from P[n/2+1] to P[n-1].
c) Recursively find the smallest distances in both subarrays. Let the distances be dl and dr. Find the minimum of dl and dr. Let the minimum be d.
d) From above 3 steps, we have an upper bound d of minimum distance. Now we need to consider the pairs such that one point in pair is from left half and other is from right half. Consider the vertical line passing through passing through P[n/2] and find all bugs whose x coordinate is closer than d to the middle vertical line. Build an array strip[] of all such bugs.
e) Sort the array strip[] according to y coordinates. This step is O(nLogn). It can be optimized to O(n) by recursively sorting and merging.
f) Find the smallest distance in strip[]. This is tricky. From first look, it seems to be a O(n^2) step, but it is actually O(n). It can be proved geometrically that for every point in strip, we only need to check at most 7 bugs after it (note that strip is sorted according to Y coordinate). See this for more analysis.
g) Finally return the minimum of d and distance calculated in above step (step 6)
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 bugs in two sets and recursively calls for two sets. After dividing, it finds the strip in O(n) time, sorts the strip in O(nLogn) time and finally finds the closest bugs in strip in O(n) time. So T(n) can expressed as follows
T(n) = 2T(n/2) + O(n) + O(nLogn) + O(n)
T(n) = 2T(n/2) + O(nLogn)
T(n) = T(n x Logn x Logn)

#include <stdio.h>
#include <float.h>
#include <stdlib.h>
#include <math.h>

int main()
{
//Enter co-ordinates of bugs
bugs P[] = {{21, 34}, {12, 30}, {40, 50}, {5, 1}, {12, 10}, {3, 4}};
int n = sizeof(P) / sizeof(P[0]);
printf("The smallest distance is %f ", closest(P, n));
return 0;
}

struct bugs
{
int x, y;
};
int compareX(const void* a, const void* b)
{
bugs *p1 = (bugs *)a, *p2 = (bugs *)b;
return (p1->x - p2->x);
}
int compareY(const void* a, const void* b)
{
bugs *p1 = (bugs *)a, *p2 = (bugs *)b;
return (p1->y - p2->y);
}
float dist(bugs p1, bugs p2)
{
return sqrt( (p1.x - p2.x)*(p1.x - p2.x) +
(p1.y - p2.y)*(p1.y - p2.y)
);
}
  
float bruteForce(bugs P[], int n)
{
float min = FLT_MAX;
for (int i = 0; i < n; ++i)
for (int j = i+1; j < n; ++j)
if (dist(P[i], P[j]) < min)
min = dist(P[i], P[j]);
return min;
}
float min(float x, float y)
{
return (x < y)? x : y;
}
float stripClosest(bugs strip[], int size, float d)
{
float min = d; // Initialize the minimum distance as d
  
qsort(strip, size, sizeof(bugs), compareY);  
  
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;
}
  
float closestUtil(bugs P[], int n)
{
// If there are 2 or 3 bugs, then use brute force
if (n <= 3)
return bruteForce(P, n);
  
// Find the middle point
int mid = n/2;
bugs midbugs = P[mid];
  
float dl = closestUtil(P, mid);
float dr = closestUtil(P + mid, n-mid);
  
// Find the smaller of two distances
float d = min(dl, dr);
  
bugs strip[n];
int j = 0;
for (int i = 0; i < n; i++)
if (abs(P[i].x - midbugs.x) < d)
strip[j] = P[i], j++;
  
// Find the closest bugs in strip. Return the minimum of d and closest
// distance is strip[]
return min(d, stripClosest(strip, j, d) );
}
  

float closest(bugs P[], int n)
{
qsort(P, n, sizeof(bugs), compareX);
  
// Use recursive function closestUtil() to find the smallest distance
return closestUtil(P, n);
}

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.