7
$\begingroup$

Given a finite set $S$ of points in $\mathbb R^p$ and a number $\rho$, my collaborators and I want to find, for each $s\in S$, the other points in $S$ that are within $\rho$ of $s$. Of course there's the obvious $O(|S|^2)$ algorithm, and we also came up with something (roughly, sort in each dimensions, then for each dimension and for each element of $S$ mark nearby points in some sparse matrices, and then combine the sparse matrices) that has better running time under certain assumptions, but not in the worst case.

I feel that this must be a standard problem, but I haven't been able to find references. I was wondering if someone here knows what I should search for or can suggest a good reference to start from?

Thanks in advance!

Improve this question
$\endgroup$
5
  • $\begingroup$ Isn't the output potentially of size $|S|^2$? $\endgroup$
    – Peter Taylor
    Commented Jan 18, 2011 at 14:26
  • $\begingroup$ 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. $\endgroup$
    – user3317
    Commented Jan 18, 2011 at 14:34
  • $\begingroup$ 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. $\endgroup$
    – user3317
    Commented Jan 18, 2011 at 14:52
  • 1
    $\begingroup$ en.wikipedia.org/wiki/Nearest_neighbor_search $\endgroup$
    – Radu GRIGore
    Commented Jan 18, 2011 at 15:31
  • $\begingroup$ 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. $\endgroup$
    – user3548
    Commented Jan 30, 2011 at 21:15

4 Answers 4

Reset to default
8
$\begingroup$

I think what you are looking for is the Fixed-radius near neighbors problem.

Improve this answer
$\endgroup$
0
4
$\begingroup$

In high dimensions you can use LsH (locality sensitive hashing) for this. In low dimensions, any data-structure for approximate nearest neighbor can answer your question approximately. However, a much easier scheme is to use a grid of appropriate size, and for each point retrieve all the points stored in its grid cell and adjoining grid cells.

In low dimensions, [CK95] showed that for each point one can compute its $k$ nearest neighbors in $O(n \log n + n k )$ time. Not quite your question, but a pretty surprising related result.

[CK95] P. B. Callahan and S. R. Kosaraju. A decomposition of multidimensional point sets with applications to k-nearest-neighbors and n-body potential fields. J. Assoc. Comput. Mach., 42:67–90, 1995.

Improve this answer
$\endgroup$
2
$\begingroup$

I don't have enough reputation to write in the comment area, so here are some things you may wish to consider (in lieu of a real answer):

Quad-trees: http://en.wikipedia.org/wiki/Quadtree Once you have built your tree based on the points in S, then eliminating distant points becomes a trivial problem and you only need to compare each point against a small subset of S.

Also, keep in mind the reflexive distance property of points. You don't have to resort to a O(S^2) algorithm since once you compared the first point with all other points, it doesn't need to be compared again. n points would require, at most, (n/2)(n-1) comparisons.

If you need higher dimensions, use octrees (http://en.wikipedia.org/wiki/Octree) or kD-trees (http://en.wikipedia.org/wiki/Kd-tree) in place of the quad-tree.

Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ (n/2)(n-1) is $O(n^2)$. (In fact it's $\Theta(n^2)$). $\endgroup$
    – Peter Taylor
    Commented Jan 18, 2011 at 16:12
0
$\begingroup$

BK Trees? http://en.wikipedia.org/wiki/BK-tree

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.