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?
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$