10
$\begingroup$

Given a set of points $x_1, \ldots, x_n \in \mathbb{R}^2$ and a radius $r$. Which is the complexity of finding the point with higher number of points at a distance smaller than $r$. E.g the one that maximizes $\sum_{i=1}^n \mathbb{1}_{\|x - x_i\| \leq r}$?

A brute force algorithm would be to go over every point and count the number of points that are at distance smaller than $r$. That would give a complexity of $\mathcal{O}(n^2)$.

Is there a better approach?

Improve this question
$\endgroup$
7
  • $\begingroup$ Have you looked at quadtrees and binary space partitioning trees? I would anticipate that they might give an algorithm that is more efficient in practice, though I don't know what the worst-case asymptotic running time might be. $\endgroup$
    – D.W. ♦
    Oct 5, 2015 at 22:55
  • $\begingroup$ (The centre of the ball from the title needs to be from the set?) One idea might be to estimate whether the radius is small compared to the average distance to the nearest neighbour or on the order of the diameter (and consider approaches for these extremes (plane sweep for small $r$) and the broad space in between). $\endgroup$
    – greybeard
    Oct 6, 2015 at 6:44
  • $\begingroup$ The center of the ball should be an $x_i$ but if there is a better algorithm with out that condition I am also interested. $\endgroup$
    – Manuel
    Oct 6, 2015 at 14:44
  • $\begingroup$ It looks like a faster than $O(n)$ algorithm for the Ball Range Counting Problem is unknown. However, if you could accept a non-exact answer then you could approximate a disk by a set of squares with different orientation. For each orientation you'll have to build a Range Tree (en.wikipedia.org/wiki/Range_tree), which will allow you to count all points inside a square in $O(log^2(n) + k)$ time (k - a number of resulting points). $\endgroup$
    – HEKTO
    Oct 6, 2015 at 17:07
  • $\begingroup$ @HEKTO Are you suggesting building a structure of cost $\mathcal{O}(n\log(n))$ to query if a point lies in a rectangle at a cost $\mathcal O (log^2(n) + k)$? Then go over all points to count how many other points lie in the approximated ball? This could work, but then, what would be the memory required for such data structure? would it be lower than $\mathcal O (n^2))$? $\endgroup$
    – Manuel
    Oct 6, 2015 at 19:32

2 Answers 2

Reset to default
5
$\begingroup$

It looks like a sublinear algorithm for the Ball Range Counting Problem isn't known for now.

However, if you could accept a non-exact answer then you could approximate a disk by a set of squares with different orientation. For each orientation you'll have to build a Range Tree, which will allow you to count all points inside a square in $O(log^2(n)+k)$ time (k - a number of resulting points).

Each range tree will require $O(n \cdot log(n))$ memory, the better approximation you want the more orientations you should use. For example, two orientations will give you an octagon, which approximates a disk with area error less than 6%.

Improve this answer
$\endgroup$
3
$\begingroup$

The answer is not so simple, there is advanced study of this question in complexity theory; it seems to be studied e.g. as the following problem, which is focused around fast "spherical range counting" queries. Yes, improved theoretical bounds are possible, but these seem to be abstract algorithms that haven't been implemented by anyone. If you want actual implementations, that is a different question.

Improve this answer
$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.