Closest Set Of Points Promblem
The closest pair of points problem is a problem of computational geometry promblem: given n points in metric space, find a pair of points with the smallest distance between them.
suppose 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. Recall the following formula for distance between two points p and q.
This problem arises in a number of applications. For example, in air-traffic control, you may want to monitor planes that come too close together, since this may indicate a possible collision so we need to track out the closest pair between them.
we know that the closest pair of points can be computed in O (n2) time by performing a brute-force approach. To do that, one could compute the distances between all the n(n − 1) / 2 pairs of points, then pick the pair with the smallest distance, as illustrated below.
minDist = infinity for i = 1 to length(P) - 1 for j = i + 1 to length(P) let p = P[i], q = P[j] if dist(p, q) < minDist: minDist = dist(p, q) closestPair = (p, q) return closestPair
Although we can design it in various number of ways here is one of the possible ways where time complexity is O(n x (Logn)^2)
process:-
Input: An array of n points P[]
Output: The smallest distance between two points in the given array.
Output: The smallest distance between two points in the given array.
1) Find the middle point in the sorted array.
2) Divide the given array in two halves. The first subarray contains points from arr[0] to arr[n/2]. The second subarray contains points from arr[n/2+1] to arr[n-1].
3) 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.
4) 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 arr[n/2] and find all points whose x coordinate is closer than d to the middle vertical line. Build an array strip[] of all such points.
5) 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.
6) Find the smallest distance in S.
c code to implement the closest set of points:-
#include<stdio.h>
#include<stdlib.h>
#include<math.h>
typedef struct
{
int x,y;
}point;
int main()
{
point *p;
int i,j,**d,n,min,s,t;
printf("\n Enter the no of points::\n");
scanf("%d",&n);
d=(int **)malloc(n*sizeof(int *));
for(i=0;i<n;i++)
{
d[i]=(int*)malloc(n*sizeof(int));
}
p=(point*)malloc(n*sizeof(point));
printf("\n enter %d no of (x,y) co-ordinate points \n ",n);
for(i=0;i<n;i++)
{
scanf("%d %d",&p[i].x,&p[i].y);
}
printf("the distance matrix is:\n");
for(i=0;i<n;i++)
{
for(j=0;j<n;j++)
{
d[i][j]=sqrt(pow((p[i].x-p[j].x),2)+pow((p[i].y-p[j].y),2));
printf(" \t %d",d[i][j]);
}
printf("\n");
}
min=9999;
for(i=0;i<n;i++)
{
for(j=0;j<n;j++)
{
if(i!=j)
{
if(min>d[i][j])
{
min=d[i][j];
s=i;
t=j;
}
}
}
}
printf("\n FROM %d to %d is the minimum distance = %d ",s+1,t+1,min);
}
*********************************************************************************************************************
