Fast computation of a ball with radius r with largest number of input points

We are given a set S of n points equipped with some metric and an integer $$r>0$$. We define $$B(x,r) \subseteq S$$ (the ball with radius r centered in x) to be the set of points in S within distance r from x. We wish to develop an algorithm for finding a point $$x \in S$$ with largest $$|B(x,r)|$$. There is a simple algorithm which runs in $$\Theta(n^2)$$, under the assumption we can compute the distance between two points in constant time.

Can we do better than this asymptotically (e.g. $$O(n \log n)$$)? If not, it would be interesting to show a lower bound on its running time, as it is quite a natural problem. Do you know any problem which is similar and for which it is believed that an algorithm faster than $$\Theta(n^2)$$ does not exist? Thanks!

I asked the participants at a conference to consider this problem, and the consensus was that subquadratic time is possible, through one of two routes. (1) Lift the points to the paraboloid $$z=x^2+y^2$$. Then a halfspace in $$\mathbb{R}^3$$ is a disk in $$\mathbb{R}^2$$. Then one can use halfspace range counting results. (2) Circle counting queries in the plane have a lowerbound of $$\Omega(n^{1/3})$$, as established in the paper below. And a total complexity of $$O^*(n^{4/3})$$ for finding the optimal center should be achievable, with $$O^*$$ indicating some $$\log n$$ factors.

In short, the literature on halfspace range counting in $$\mathbb{R}^3$$, and circle counting queries in $$\mathbb{R}^2$$, should lead to subquadratic performance.

Brönnimann, Hervé, Bernard Chazelle, and János Pach. "How hard is half-space range searching?." Discrete & Computational Geometry 10, no. 2 (1993): 143-155.

• Thank you for this. Are the results extensible to other domains? In particular to domains like R^3 or R^4? Gerhard "Adding Depth To The Problem" Paseman, 2019.08.11. – Gerhard Paseman Aug 11 '19 at 19:43
• @GerhardPaseman: Most of these results are phrased in terms of dimension $d \ge 3$, often with $(1-1/d)$ factors, so, e.g., $n^{2/3}$ per query in $d=3$. But I am not an expert on this vast and complex literature. And there can be a tradeoff between preprocessing time and space, and query time. Which is why I hedged with "should" etc. The conversion between ball-counting and halfspace-counting in one dimension higher, works for arbitrary $d$. – Joseph O'Rourke Aug 11 '19 at 19:52

In general, probably not, as we do not know how the point set is distributed. If you are lucky, there are a couple things to try which may yield results quickly.

The first uses the assumption that the distances have been computed and placed in a doubly linked list sorted by length. Now start at both ends. In alternating steps, if an edge length has distance at most r, increment two counters, one for each vertex on that edge. If an edge length is greater than r, decrement two other counters, one for each vertex on that edge. Stop when the transition from less than r to more than r has been reached at either end. Now poll the appropriate set of counters to see what maximum value has been reached. If your value is close to zero or close to n, you may reach it in sub quadratic time. This works when you have one point set and lots of values of r to test, for then you can amortize the preprocessing time of sorting edges by length.

The second assumes that the metric satisfies the triangle inequality. Take some small number of points, say three, and for each point create an ordered list of distances from that point. If you are lucky, you will get a range from near zero to much greater than 2r for each distance.

Now for each vertex v, find its distance from each of the three points, and then build a list of points to check. This list will be the intersection of three other lists, each which have a distance value within r of that value v has. If all goes well, you will end up checking much fewer than n points for each v. This works when the spread of distances is substantial and r is small. If r is large, hopefully you found that out from the three initial points, and can do something else to determine the value.

Gerhard "Sometimes You Need Lucky Data" Paseman, 2019.08.07.

• thanks! Those seem to be a few practical tricks. It would be very interesting to prove a lower bound... – Mauro Sox Aug 8 '19 at 18:29

I believe in general the answer is no. Imagine that your metric space has all but one distances equal to $$3$$ and for some vertices, say $$x, y$$, we have $$d(x, y)=1$$. If $$r=2$$ then the answer is either $$x$$ or $$y$$ but to find it you at worst has to check all $$\Theta (n^2)$$ distances.