Find k nearest restaurants to customers

First what is nearest?  I assume you mean a specified distance?  Also you want this done per customer? which would make the only sense..

Is this an academic assignment?  
The sort of help you can get depends on the answer.

You might want to break you map in regions (states or grid squares for example), and then keep track of adjacent/nearby states or sqares.
Then when you get a request, you would only have to calculate accurate distances for a subset of the restaurants.

You might build a Voronoi diagram.

HI,
No its a algorithm question i found one some site.
The locations are coordinates on 2D plane. So by nearest i mean the mathematical distance between two coordinates.
So a naive approach will be to find the distance between each customer and restaurant
But this is a brute force approach , i want a better way to do it.

Normally you would have a max distance to do your calculations to narrow your search, otherwise you will be calculating every restaurant.  
Grab your customer x,y (normally lat/long)
Lets say the distance is 10 miles (dtr)
Just calculate what 10 miles is for xMin and xMax as well yMin and yMax
Lets say 1 mile=5 steps (ms)
stps=dtr*ms
xMin=x-stps
xMax=x+stps
yMin=y-stps
yMax=y+stps

Now just return any restaurants where their x is between xMin and xMax and y is between yMin and yMax

What is the value for k?    Is it known and constant?  Does the order of the k restaurants matter?

With significant preprocessing, you could make a map (like ozo's Voroni diagram) so that each region of the map is associated with the same k restaurants.  This would reduce a customer request to a look-up table.

in 2-d, you can build a k-nearest neighbor Voronoi diagram in O(k^2 N log N) time, and search it in O(k+log N) time

You can exclude the longitude and latitude based on distance so say you are at x and you only want items within x+50 yards.  You can add that distance to your longitude and latitude in all directions and exclude all others that fall out of the range.

So it would be anywhere where x+50 and x-50, same for y.  Then I'm not sure how your data is laid out, but you would search any items that falls within x first then y or both, depending if it is a sql server.

Something like that?

HI ozo
in 2-d, you can build a k-nearest neighbor Voronoi diagram in O(k^2 N log N) time, and search it in O(k+log N) time ?

Can you give me a reference where its explained to build a k-nearest neighbor voronoi diagram ?
I am not familiar with voronoi diagrams.

No its a algorithm question i found one some site.

I would say, by that the author has contradicted that the question is of academic type.

if I am right, I would like to post the description of an algorithm based on a suggestion d-glitch has made.

Sara

I added a link to the question so it is properly attributed in compliance with site rules.

I did so somewhat selfishly, because I think this is an interesting problem, and am looking forward to a good discussion. This kind of problem comes up very frequently on web pages, because a customer always wants to know where are the closest places to buy a product. Since I am frequently asked to choose the state or territory I live in, I have concluded that most web developers are not using a very good way of solving the problem.

That said, I looked up Voronoi diagrams as mentioned by ozo and find them to be an interesting approach. I don't know how to create one, but if one were available it would definitively answer the question of where the closest restaurant is located. You would also want to have available a list of Voronoi territories that are contiguous with each one of the restaurants.

After doing some more thinking about Voronoi diagrams, I realized that the kth closest restaurant must be in a Voronoi territory contiguous with one or more of the k-1 Voronoi territories previously found. This realization greatly reduces the solution space, as each new solution will lie on a spiral of Voronoi territories surrounding the first one. The proof for my assertion involves drawing a line from the customer to a restaurant in a Voronoi territory that is not contiguous with previous solutions. It can be shown that such a line will always pass through a Voronoi territory that is contiguous with previous solutions--and that the restaurant in the Voronoi territory so traversed will always be closer to the customer than the one in the non-contiguous territory.

When you find the k-1 th closest Voronoi territory, you add its contiguous Voronoi territories to the solutions space. Since there are only a handful of such territories, you can calculate the distance between each newly added restaurant and the customer. These distances will likely sort as more distant from the customer than the previously identified contiguous Voronoi territories, so it will be pretty easy to identify the kth closest one in a previously sorted list.

The diameter of the solution cloud is proportional to the square root of the number of previously identified solutions. The solution space for a new territory is proportional to the circumference of that cloud, so the solution space increases in size as the square root of the number of previous solutions.

All that said, I am now going to be quiet in hopes of learning something from ozo, d-glitch, sarabande and others, who clearly are approaching the problem from a higher level.