Find the maximum subset contained by a ball of radius R 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 &gt; 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 &gt; 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.
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.


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