Author |
Topic: Find out the nearest N points of a point P (Read 1881 times) |
|
cssomnath
Newbie
Posts: 20
|
 |
Find out the nearest N points of a point P
« on: Dec 3rd, 2004, 5:01am » |
 Quote  Modify
|
In a 3D space there are millions of points. And also a particular point P is given. Find the nearest N points of the point P.
You can use your own convenient representation of the points. I heard that this question was asked in Amazon Interview and it is possible to solve in O(N).
|
|
 IP Logged |
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender: 
Posts: 7527
|
|
Re: Find out the nearest N points of a point P
« Reply #1 on: Dec 3rd, 2004, 5:29am » |
Quote Modify
|
There are 2 numbers to consider: M, the total number of points ("millions of points") and N, the number of points to find.
If M is constant, it is O(1) for any N. If M grows like N^2, it is obviously not possible to do O(N), since you need to look at least once to every N^2 points. Same if N is constant and M grows.
So I assume M grows linearily with N?
|
|
IP Logged |
|
|
|
cssomnath
Newbie
Posts: 20
|
|
Re: Find out the nearest N points of a point P
« Reply #2 on: Dec 3rd, 2004, 5:36am » |
Quote Modify
|
Yes I thought of that. Can we do it in O(M) anyway where M is the total number of points and you have to find out N nearest points out of that. Assuming M and N are not constant
|
|
IP Logged |
|
|
|
Miles Teg
Newbie
Gender:
Posts: 11
|
|
Re: Find out the nearest N points of a point P
« Reply #3 on: Dec 3rd, 2004, 8:31am » |
Quote Modify
|
Do you mean , we preprocess the points to a structure and then asked about a point and have to answer .
Or just given unstructured M points and then have to answer.
|
|
IP Logged |
|
|
|
Barukh
Uberpuzzler
Gender:
Posts: 2276
|
|
Re: Find out the nearest N points of a point P
« Reply #4 on: Dec 3rd, 2004, 9:33am » |
Quote Modify
|
[smiley=blacksquare.gif]
What we actually need is to find the N-th nearest point. Then, a simple comparision with the distance to this point (linear time) gives all needed points.
This problem is known under the name "Selection". Fortunately, there exist worst-case linear algorithms to solve it - look here for the nice explanation.
[smiley=blacksquare.gif]
|
|
IP Logged |
|
|
|
cssomnath
Newbie
Posts: 20
|
|
Re: Find out the nearest N points of a point P
« Reply #5 on: Dec 4th, 2004, 1:43am » |
Quote Modify
|
Sorry. Let me clarify. Distance of each point from P is not known. All you have the coordinates of the M points and you know the point P. Now we have to find out N nearest points. If we can find out at least O(M) algo that is not bad. You can use multiple processors if you want.
|
|
IP Logged |
|
|
|
Barukh
Uberpuzzler
Gender:
Posts: 2276
|
|
Re: Find out the nearest N points of a point P
« Reply #6 on: Dec 4th, 2004, 10:40am » |
Quote Modify
|
on Dec 4th, 2004, 1:43am, cssomnath wrote:| Sorry. Let me clarify. Distance of each point from P is not known. All you have the coordinates of the M points and you know the point P. |
|
What does it mean that you know the point P? I assume you know its coordinates – like you know the coordinates of all other points. Then, the distance between any point Q and P is the square root of the following quantity:
(xQ - xP)2 + (yQ -yP)2 + (zQ - zP)2
Quote:| If we can find out at least O(M) algo that is not bad. You can use multiple processors if you want. |
|
I don’t see any reason to use multiple processors for the O(M) algorithm. Am I missing something?
|
| « Last Edit: Dec 4th, 2004, 10:40am by Barukh » |
IP Logged |
|
|
|
cssomnath
Newbie
Posts: 20
|
|
Re: Find out the nearest N points of a point P
« Reply #7 on: Dec 5th, 2004, 6:21am » |
Quote Modify
|
on Dec 4th, 2004, 10:40am, Barukh wrote:
What does it mean that you know the point P? I assume you know its coordinates – like you know the coordinates of all other points. Then, the distance between any point Q and P is the square root of the following quantity:
(xQ - xP)2 + (yQ -yP)2 + (zQ - zP)2 |
|
Yes point P is given means you know the coordinate of the point P (nothing special about that). Also you know the coordinates of all other points. But the distance of each point from P is *not* known so you have to calculate each distance. The formula you have given is correct and you can use that.
Calculating the distance of each point (there are M such points) straight away makes the algo O(M). You have to find out N nearest points of P. Can we do that in O(M) also?
Actually the interviewer first asked my friend to solve it in O(1) and then in O(M). I thought O(1) if at all possible can only be done using multiple processors.
|
| « Last Edit: Dec 5th, 2004, 6:27am by cssomnath » |
IP Logged |
|
|
|
Barukh
Uberpuzzler
Gender:
Posts: 2276
|
|
Re: Find out the nearest N points of a point P
« Reply #8 on: Dec 5th, 2004, 9:03am » |
Quote Modify
|
on Dec 5th, 2004, 6:21am, cssomnath wrote:Yes point P is given means you know the coordinate of the point P (nothing special about that). Also you know the coordinates of all other points. But the distance of each point from P is *not* known so you have to calculate each distance. The formula you have given is correct and you can use that.
Calculating the distance of each point (there are M such points) straight away makes the algo O(M). You have to find out N nearest points of P. Can we do that in O(M) also? |
|
I think the answer is yes, and I demonstrated it in my previous post (#4). What is wrong with it?
|
|
IP Logged |
|
|
|
cssomnath
Newbie
Posts: 20
|
|
Re: Find out the nearest N points of a point P
« Reply #9 on: Dec 5th, 2004, 9:15am » |
Quote Modify
|
You need to find N nearest points *not* the Nth nearest point (total N points out of M points).
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Find out the nearest N points of a point P
« Reply #10 on: Dec 5th, 2004, 11:15am » |
Quote Modify
|
Yes, but if you first find the Nth nearest point, you can use it to find the N nearest ones.
It's just a partial sorting on distance, every point with a distance to P smaller than the Nth point belongs to the N nearest points. This takes O(M) time once you have found the Nth point. So, if you can find the Nth nearest point in O(M) time, you can solve the whole problem in O(M) time.
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
gniv
Newbie
Gender:
Posts: 19
|
|
Re: Find out the nearest N points of a point P
« Reply #11 on: Feb 21st, 2005, 10:06am » |
Quote Modify
|
on Dec 3rd, 2004, 5:01am, cssomnath wrote:In a 3D space there are millions of points. And also a particular point P is given. Find the nearest N points of the point P.
You can use your own convenient representation of the points. I heard that this question was asked in Amazon Interview and it is possible to solve in O(N).
|
|
I don't think selection is the desired answer here. Since this was given in an interview, the exact wording is very important. If cssomnath wrote it ad literam, then it's a bit of a trick question, ant it can be done in O(N) indeed:
Since we are given the point P and we can choose to represent the points as we see fit, we can store the points in sorted order on the distance from P. Then all we have to do to report the nearest N points is to walk through the sorted array. This way, even an O(1) solution is conceivable.
|
|
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print