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?
Asked By : Manuel
Answered By : HEKTO
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%.
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/47913
0 comments:
Post a Comment
Let us know your responses and feedback