Algorithm – Finding closest pair of points
Technique – using Divide and Conquer strategy
Problem – We are given a set of points and we have to find the minimum distance between all the
Points.
Solution-
1. Naïve Approach – we can loop through all the set of points one by one for each point.
Algorithm –
float distance( point p1, point p2) //distance between two coordinates
{
return sqrt((p2.x-p1.x)*(p2.x-p1.x)+(p2.y-p1.y)*(p2.y-p1.y));
}
float naive(point p[], int n) // point is the structure having x , y as members(coordinates)
//& n = total number of points available
{
int i , j ;
float min=FLT_MAX; // defined constant
float dist;
for(i=0;i<n;i++) // iterating through each point
{
for(j=i+1;j<n;j++) // for each point check its distance from remaining points
{
dist = distance(p[i], p[j]);
if(dist < min)
min = dist;
}
}
return min;
}
Time Complexity – O(n^2)
2. Divide and Conquer Approach – we can better the naïve approach using divide and conquer strategy.
Steps –
Pre- processing step - Sort the given points according to the x coordinates.
1. Find the middle point.
2. Recursively find the minimum distance in the left and right sub arrays.
Understand this step – we can find the minimum distance either on the left side of the mid-point (left sub array) or on the right side (right sub array) or we can find minimum on the points among which one is in the left sub array and another in the right sub array.
3. Among both the minimums (from left and from right), find the minimum, let us call it d.
4. Now comes the important step-
We find those points whose distance is less than d from the middle point (found in 1.) in both (left and right) directions
As only these could be the candidates for those points whose distance is closest.
5. Sort these points according to the y coordinate
6. Find the minimum among all these points using the naïve approach but it is been proved that inner loop runs at most 6 times.
(check this- http://people.csail.mit.edu/indyk/6.838-old/handouts/lec17.pdf) .
7. Now find the minimum between the point found in 7 and d.
Time Complexity – time for divide and conquer – 2T(n/2) // as dividing into two sub parts of n/2
// size
+ time for finding the points having distance < d (step 4) – O(n)
+ time to sort( step 5) – O(nlogn)
+ step 6 – O(n) because the inner loop runs at most 6 times
=) O(nlognlogn)
Algorithm -
struct point // point representation
{
int x, y;
};
// for sort stl
int cmpx(const point& p1, const point& p2)
{
return (p1.x<p2.x);
}
int cmpy(const point& p1, const point& p2)
{
return (p1.y<p2.y);
}
// step 5 & 6 , strip is the array consisting of “certain points” from left and right sub arrays
float stripclosest(point strip[] , int j ,float d)
{
// d is the min (corresponding to min of naive)
// j - #points in strip
//5. sort strip acc to y coordinates
sort(strip, strip+j, cmpy);
int n =j;
float dist;
//6. find minimum using naive approach .. it takes O(n) not O(n^2) because inner loops
// runs atmost 6 times
for(int i=0;i<n;i++)
{
// if distance of points is less than d , only then consider otherwise no need as that pair can never
// be closest point(obviously)
for(int k=i+1;k<n && abs(strip[k]. y - strip[i].y) < d; k++)
{
dist = distance(strip[i], strip[k]);
if(dist < d) // if less than the considered minimum
{
d = dist;
}
}
}
return d ;
}
float closestutil(point p[], int n)
{
// Base Case
if(n<=3)
return naive(p, n);
//2. find mid point
int mid = n/2;
point m = p[mid];
//3a. recursively find minimum in left and right sub arrays
float dl = closestutil(p, mid);
float dr = closestutil(p+mid, n-mid);
//3b. find minimum among both
float d = minimum(dl, dr);
//4. make an array strip and store the point having distance <d from point m
point strip[n];
int j=0;
for(int i=0;i<n;i++)
{
// take only if the distance of point is less than d from the middle line(point) as only they can be the //candidates for the points having closest distance
if(abs(p[i].x-m.x) < d)
{
strip[j]=p[i];
j++;
}
}
// calculating smallest distance in strip and finding minimum among d(min of left and right and min //distance in strip(min if the closest distance is present in subarray crossing some part of left and //right sub array)
return minimum(d, stripclosest(strip, j, d, a));
}
float closest(point p[], int n)
{
//1. sort the points acc to x coordinate
sort(p, p+n, cmpx);
return closestutil(p,n);
}
Before going further do try to code it and if any problem occurs or you have any doubt regarding any thing related to the algorithm or any query please kindly tell us either on our Facebook Group
https://www.facebook.com/groups/logicheap/or you can follow our twitter account - https://twitter.com/Logic_Heap
For more such algorithms and many more videos and stuff related to algorithms of data structures, kindly subscribe to our YouTube channel -https://www.youtube.com/watch?v=FFOTq1RcrBE
Implementation in C++
// prints distance and corresponding points also
#include <iostream>
#include<bits/stdc++.h>
using namespace std;
struct point
{
int x, y;
};
// for qsort stl
int cmpqx(const void* u, const void* v)
{
point *p1 =(point*)u;
point *p2= (point*)v;
return (p1->x - p2->x);
}
int cmpqy(const void* u, const void* v)
{
point *p1 =(point*)u;
point *p2= (point*)v;
return (p1->y - p2->y);
}
// for sort stl
int cmpx(const point& p1, const point& p2)
{
return (p1.x<p2.x);
}
int cmpy(const point& p1, const point& p2)
{
return (p1.y<p2.y);
}
float minimum(float i, float j)
{
return (i<j?i:j);
}
float distance( point p1, point p2)
{
return sqrt((p2.x-p1.x)*(p2.x-p1.x)+(p2.y-p1.y)*(p2.y-p1.y));
}
void printpoint(point a[])
{
cout<<"\n"<<a[0].x<<" "<<a[0].y;
cout<<"\n"<<a[1].x<<" "<<a[1].y;
}
//O(n^2)
float naive(point p[], int n, point a[])
{
int i , j ;
static float t=INT_MAX;
// making it static is necessary otherwise suppose that min is found in left subarray and now right //subarray is called and t will not hold the previous min value and calculate the min and point array //will be wrong
//I advise you to go and remove static and execute and you will understand the power of static //yourself.
float dist;
for(i=0;i<n;i++)
{
for(j=i+1;j<n;j++)
{
dist = distance(p[i], p[j]);
cout<<"\n checking t="<<t;
if(dist < t)
{
t = dist;
a[0].x = p[i].x;
a[0].y = p[i].y;
a[1].x = p[j].x;
a[1].y = p[j].y;
}
}
cout<<"\n checking returning t ="<<t;
return t;
}
float stripclosest(point strip[] , int j ,float d, point a[])
{
// d is the min (corresponding to min of naive)
// j - #points in strip
//5. sort strip ac to y coordiantes
qsort(strip, j , sizeof(point), cmpqy);
//sort(strip, strip+j, cmpy); , you can use any but qsort is better
int n =j;
float dist;
//6. find minimum using naive approach .. it takes O(n) not O(n^2) because inner loops
// runs atmost 6 times
for(int i=0;i<n;i++)
{
for(int k=i+1;k<n && abs(strip[k]. y - strip[i].y) < d; k++)
{
dist = distance(strip[i], strip[k]);
if(dist < d)
{
d = dist;
a[0].x = strip[i].x;
a[0].y = strip[i].y;
a[1].x = strip[k].x;
a[1].y = strip[k].y;
}
}
}
return d ;
}
float closestutil(point p[], int n, point a[])
{
if(n<=3)
return naive(p, n, a);
//2. find mid point
int mid = n/2;
point m = p[mid];
//3a. recursively find minimum in left and right sub arrays
float dl = closestutil(p, mid,a);
float dr = closestutil(p+mid, n-mid,a);
//3b. find minimum among both
float d = minimum(dl, dr);
//4. make an array strip and store the point having distance <d from point m
point strip[n];
int j=0;
for(int i=0;i<n;i++)
{
if(abs(p[i].x-m.x)<d)
{
strip[j]=p[i];
j++;
}
}
// calculating smallest distance in strip and finding minimum among d(min of left and right)
// and min dist in strip(min if the closest distance is present in subarray crossing some part of
//left and right sub array)
return minimum(d, stripclosest(strip, j, d, a));
}
float closest(point p[], int n, point a[])
{
//1. sort the points acc to x coordinate
//qsort(p, n, sizeof(point), cmpqx);
sort(p, p+n, cmpx);
return closestutil(p,n, a);
}
int main() {
point p[] = {{2, 3}, {12, 30}, {40, 50}, {5, 1}, {12, 10}, {3, 4}};
point a[2];
int n = sizeof(p) / sizeof(p[0]);
printf("The smallest distance is %f ", closest(p, n, a));
printpoint(a);
return 0;
}
Monday, 27 July 2015
Finding closest pair of points
Subscribe to:
Post Comments (Atom)
No comments:
Post a Comment