Find the maximum subset contained by a ball of radius R

Question

I am searching for the name of / literature to the algorithmic problem as follows:

Given a metric space $(M,d)$, a finite Subset $X = \{ x_1, \dots, x_n \} \subset M$ and a fixed Radius $R > 0$, find the maximum amount of points being enclosed by a ball of radius $R$. Alternatively, find $N$, such that $ N = \max_{x \in M} |X \cap B_R(x)| $

I only know of the 1-center problem so far. But this tries to solve the problem for minimizing the radius of a ball containing all points within a set. I also found one paper discussing a $\mathcal{O}(|X|^2)$ solution for the euclidean plane. There it has been called Maximum-Enclosing-Disk-Problem. Any information regarding generalizations for $\mathbb{R}^D, D > 2$ or different metrics, would be helpful.

I am not very experienced with computational geometry and the theory of algorithms, but I need to find current literature on this problem. Having a name, or a similar problem, on which this problem can be reduced, would be help me a lot. Also, if you know literature or keywords regarding approximation attempts.

Thank you for your answers.

Edit: As discussed in the comments, an arbitrary metric space might not even computable. However, as I didn't want to restrict the solution on real euclidean spaces (e.g. the space of strings provided with the edit-distance should be an option), I decided for the very general formulation of the problem.

Answer 1

Here is a slightly-better-than-raw-brute-force algorithm for $D$-dimensional Euclidean space. It's about as trivial as you can get with this kind of problem short of "check all subsets of points for being in a disk of radius at most $R$", but I figure it's nontrivial enough to serve as a baseline for future answers.

Suppose you have a disk that contains a collection of points, say the optimal disk that you're looking for. Unless there are points on its boundary, you can wiggle this disk around/shrink its radius to contain the exact same collection of points. Hence there can be many optimal choices of the disk. The main idea here is to focus only on disks that are easy to describe, namely those which are determined by some points on the boundary. With this restriction, we'll only need to consider a finite number of disks, and the rest of the algorithm will just be to enumerate all of these disks and count how many points each contains.

So now focus on a particular disk containing a fixed set of points. With translations, you can get one point on the boundary. We now consider some cases, which I'll outline for $D = 3$, though they generalize.

1. If we have exactly one point on the boundary, imagine moving the center of the disk toward that boundary point and shrinking the radius so that the boundary point stays on the boundary. As we do this, one of two things happens: either the radius gets to zero without any other points crossing the boundary (in which case the disk contained only a single point in the first place), or else some other point enters the boundary.

2. If we have exactly two points on the boundary, this forces the center to lie in the plane of points equidistant to the two points on the boundary. Now imagine moving the center toward the midpoint of the two boundary points, and adjusting the radius accordingly. One of two things happens: the center reaches the midpoint of the two boundary points without any additional points crossing the boundary, or else some point enters the boundary. In the first case, we have two antipodal points on the sphere (which determines the disk); in the second case, we now have a collection of three (non-colinear) points on the boundary.

3. There are three non-colinear points on the boundary, but every collection of four or more is coplanar. Consider the plane defined by the boundary points, and draw the circle defined by them within this plane. This circle is included in the boundary of the disk, and moreover the center of the disk must lie on the line perpendicular to the plane running through the center of the circle. Consider moving the center of the sphere along this line, toward the center of the circle, and adjusting the radius accordingly. One of two things happens: either the center of the disk reaches the center of the circle without any points crossing the boundary, or else a new point (not on the plane defined by the initial boundary points) enters the boundary. In the first case, we have some three non-colinear points on a greater circle on the disk (which determines the disk); in the second case, we have at least four non-coplanar points on the boundary.

4. Finally, the case where we have at least four non-coplanar points on the boundary. Here (in $D = 3$), this completely determines the disk.

It follows that you can enumerate every collection of $1, 2, \ldots, D+1$ points, compute the appropriate disk, check that its radius is at most $R$, and then count the number of points in it. You can compute the disk in time $O(D)$ in each case, and you can naively count the points inside the sphere in $O(n\cdot D)$ time. This gives an overall time of $O(D\cdot n^{D+2})$.

If you know some more information about what your input looks like, there are very likely to be some heuristic optimizations you can put on top of this algorithm. A simple example is ignoring any collection containing two points with distance greater than $2\cdot R$.

Answer 2

As my original question was asking for literature and scientific references, I consider posting a matching reference as a self-answer to this question:

I have found an article discussing an approximation attempt and lower bounds for both the exact and the approximated problem in the $D$-dimensional euclidean space.

It is not exactly the same version of the problem as stated above, but very similar:

Given a set of $n$ points with positive real weights in $d$-dimensional space, we consider an approximation to the problem of placing a unit ball, in order to maximize the sum of the weights of the points enclosed by the ball. Given an approximation parameter $ε < 1$, we present an $\mathcal{O}(\frac{n}{ε^{d−1}})$ expected time algorithm that determines a ball of radius $1 + ε$ enclosing a weight at least as large as the weight of the optimal unit ball. This is the first approximate algorithm for the weighted version of the problem in $d$-dimensional space. We also present a matching lower bound for a certain class of algorithms for the problem.

http://www.sciencedirect.com/science/article/pii/S0020019009002609 http://fc.isima.fr/~fonseca/enclosing-IPL.pdf

Answer 3

Feasibility: ​ uses the existential theory of the reals

By Proposition 4.1 (on page 290), there is an algorithm (the same for each of the following)
that for fixed $\big[D$ and algebraic definition of "is in the ball of radius $R$ centered at"$\big]$,
puts the resulting problem on $\mathbb{R}^D$ in NC.
When we let those vary, both exponents (with wikipedia's choice of variables, $c$ and $k\hspace{.02 in}$) will
grow at-most-linearly in the number of variables needed to express the relevant inequalities.
(Basically, those exponents will grow linearly in $D$.)

Hardness: ​ ​ ​ Reduce from MAX-3SAT $\color{grey}{\text{or MAX-4SAT instead}}$ to the $\ell_{\hspace{-0.04 in}\infty}$ metric.


For each clause ​ $\color{grey}{w\vee \hspace{.02 in}}x\vee y\vee z$ , ​ create variables $a$ and $b$ and the terms $\color{grey}{\lnot a\land \lnot b\land w \hspace{.15 in},}\hspace{.12 in}a\land \lnot b\land x\hspace{.15 in},\hspace{.09 in}a\land b\land y\hspace{.15 in},\hspace{.15 in}\lnot a \land b\land z \hspace{.3 in}$.
Clearly, any assignment satisfies at most one of those terms, and any assignment that does satisfy one of those terms also satisfies ​ $\color{grey}{w\vee \hspace{.02 in}}x\vee y\vee z$ . ​ ​ ​ Conversely, whenever ​ $\color{grey}{w\vee \hspace{.02 in}}x\vee y\vee z$ ​ is true, there will be a choice of ​ $a,\hspace{-0.02 in}b$ ​ that satisfies at least one of those terms.
Thus the maximum number of satisfiable clauses will equal the maximum number
of satisfiable terms, and the assignments satisfying that number of clauses will
be exactly those induced by assignments which satisfy that number of terms.

The previous paragraph won't produce such terms, but if in general,
simplify the MAX-3DNF-SAT instance by removing terms with contradictory literals.
Let ​ $D,\hspace{-0.02 in}m$ ​ be the number of variables,terms respectively in the simplified instance.
Temporarily assume that ​ $6/5 \leq R < 13/10$ . ​ ​ ​ Take an initially empty multiset. ​ ​ ​ For each of the ​ $2\hspace{-0.05 in}\cdot \hspace{-0.04 in}D$ ​ coordinate directions, put in ​ $m\hspace{-0.04 in}+\hspace{-0.06 in}1$ ​ points $2$ away from the origin in that direction. ​ ​ ​ For each term, put in a point such that [for each variable $v$ in the term, the point's $v$ coordinate is $\pm 1$ as determined by the literal's sign] and that point's other coordinates are all zero. ​ Now, move them around by less than $1/5$ so we get an actual set rather than just a multiset. ​ ​ ​ For any assignment to the MAX-3DNF-SAT instance, the induced point in ​ $\{\hspace{-0.02 in}-1,\hspace{-0.04 in}\scriptsize+\normalsize 1\hspace{-0.04 in}\}^D$ ​ is within $R$ of each point in $[D$ of the groups of ​ $m\hspace{-0.04 in}+\hspace{-0.05 in}1$ ​ points$]$, and also within $R$ of the points corresponding to the terms it satisfies.

Conversely, since only $m$ points in the set come from terms,
optimal balls must intersect at least $D$ of the groups of ​ $m\hspace{-0.04 in}+\hspace{-0.05 in}1$ ​ points.
Those groups are all more than $9/5$ away from the origin in their coordinate direction,
so optimal ball-centers can't have coordinates with absolute value less-than-or-equal-to $1/2$,
and no such ball can intersect opposite groups of ​ $m\hspace{-0.04 in}+\hspace{-0.05 in}1$ ​ points.
In particular, such balls intersect at most $D$ of the groups of ​ $m\hspace{-0.04 in}+\hspace{-0.05 in}1$ ​ points, and the coordinates
of such centers are all non-zero, so they induce an assignment to the Boolean variables.
The points that come from terms are all more than $4/5$ in each of their literal's directions,
so can only be within an optimal ball if they are satisfied by the assignment which is
induced by the ball's center. ​ By the previous paragraph's last sentence, that means the
centers of optimal balls induce assignments which satisfy a maximum number of terms.

If $R$ is not in $[6/5,\hspace{-0.05 in}13/10)$, then just divide all distances by ​ $4/(5\hspace{-0.05 in}\cdot \hspace{-0.05 in}R)$ .
That completes the reduction from MAX-3SAT $\color{grey}{\text{and MAX-4SAT}}$ to the
version of your problem with the $\ell_{\hspace{-0.04 in}\infty}$ metric in which $R$ is just approximate.

Answer 4

A first intuition is to check all possible balls centered at $x_i$. It may not be optimal, but intuitively it might be possible to prove a approx ratio.