## Monday, August 3, 2009

### Finding the closest points in rectangular region

Hi,
suppose in XY plane if some arbirary no. of points (xi,yi)'s are given and given some input (x,y) , how can we find out n closest points to the given input point (x,y)?
please try some efficient algo...

Let's say the total number of points in XY plane is N. We have to find n << N points closer to some point (x,y).
I was looking for a solution; which doesn't depend of N. Can we find out those n points without going through all N points?

Comment:
suppose there are one milloin points in the plane..then scanning through all the points takes O(1 million) time which is really bad( in case we need some 100 points closer to given point)..
we need some efficient sol.
Thanks

For each (xi,yi) in the plane
{
Consider a circle with center (x,y) and radius distance( (x,y),(xi,yi) )

stack=clear;
inside=0;
push(xi,yi)
For each other point (xj,yj) in the plane(other than the circled point)
{

if point lies inside circle
{
inside++;
push(xj,yj)
}

if(inside>n-1)
{
break
inside=0;
}

}

if(inside==n)
pop all elements from stack and print them

}

The complexity will be no. of points*no. of points

Is This Correct??