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