Timeline for Find all nearby points in a set, for each element of the set
Current License: CC BY-SA 2.5
12 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jan 30, 2011 at 23:21 | answer | added | sclv | timeline score: 0 | |
| Jan 30, 2011 at 21:15 | comment | added | user3548 | Hi Oosterwal, SqrRoot((Xc-Xa)^2 + (Yc-Ya)^2) < r Where: Xc = (set of x coordinates of all points) - specific (Xa) coordinate Yc = (set of y coordinates of all points) - specific (Ya) coordinate r = radius distance required. Note that the formula using '<' is obviously meaning 'Within'. Use '<=' if the points can be equal to the radius in question. Progammatically: for each s in S Select * from S Where sqrt((S(Xc)-s(Xa)^2 + (S(Yc)-s(Ya))^2)) < r This will work for two-Dimensional set of points with a radial distance. | |
| Jan 20, 2011 at 4:13 | answer | added | Sariel Har-Peled | timeline score: 4 | |
| Jan 18, 2011 at 22:55 | history | tweeted | twitter.com/#!/StackCSTheory/status/27499383931011072 | ||
| Jan 18, 2011 at 16:06 | answer | added | oosterwal | timeline score: 2 | |
| Jan 18, 2011 at 15:40 | answer | added | Vinicius dos Santos | timeline score: 8 | |
| Jan 18, 2011 at 15:31 | comment | added | Radu GRIGore | en.wikipedia.org/wiki/Nearest_neighbor_search | |
| Jan 18, 2011 at 14:52 | comment | added | user3317 | Another thing: Other assumptions are possible for us, as are approximations. Most of all, I just want to know what kind of solutions are already out there, and where to look for them. | |
| Jan 18, 2011 at 14:34 | comment | added | user3317 | That's true. I should have mentioned that for us usually $\rho$ is much smaller than the diameter of $S$. If the maximum number (over $s\in S$ of points in $S$ within $\rho$ of $s$ is $M$, then we'd ideally like an algorithm that is $O(M|S|)$. Or something like that. | |
| Jan 18, 2011 at 14:29 | history | edited | user3317 | CC BY-SA 2.5 |
added 3 characters in body
|
| Jan 18, 2011 at 14:26 | comment | added | Peter Taylor | Isn't the output potentially of size $|S|^2$? | |
| Jan 18, 2011 at 14:22 | history | asked | user3317 | CC BY-SA 2.5 |