# Complexity for finding a ball that maximizes the number of points lying in it

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?

• 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. – D.W. Oct 5 '15 at 22:55
• (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). – greybeard Oct 6 '15 at 6:44
• 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. – Manuel Oct 6 '15 at 14:44
• 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). – HEKTO Oct 6 '15 at 17:07
• @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))$? – Manuel Oct 6 '15 at 19:32

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%.