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

<p>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.</p>

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

<blockquote>
  <p>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 $ε &lt; 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.</p>
</blockquote>

<p><a href="http://www.sciencedirect.com/science/article/pii/S0020019009002609" rel="nofollow">http://www.sciencedirect.com/science/article/pii/S0020019009002609</a>
<a href="http://fc.isima.fr/~fonseca/enclosing-IPL.pdf" rel="nofollow">http://fc.isima.fr/~fonseca/enclosing-IPL.pdf</a></p>

CC BY-SA 3.0
2016-06-17T13:43:11.423Z
2016-06-17T13:43:11.423Z
Jonas Köhler
<p>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.</p>

<p>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.</p>

<p>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.</p>

<ol>
<li><p>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.</p></li>
<li><p>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.</p></li>
<li><p>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.</p></li>
<li><p>Finally, the case where we have at least four non-coplanar points on the boundary. Here (in $D = 3$), this completely determines the disk.</p></li>
</ol>

<p>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})$.</p>

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

CC BY-SA 3.0
2016-06-16T15:14:36.577Z
2016-06-16T15:14:36.577Z
Andrew Morgan
<p>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.</p>

CC BY-SA 3.0
2016-06-16T13:38:29.393Z
But this would be very restrictive. Imagine a square of four points $x_1, \dots, x_4$ in the real plane with side length $\frac{R}{\sqrt{2}}$. Any $R$-ball centered at one of these points would only capture three points, whereas the optimal solution would be taking the center of mass returning 4  as the correct maximum number.

An (intuitive) approximation idea would be taking the sets of $R$-neighbors in $X$ for every $x \in X$ as they are candidate sets and proceed with a classical optimization procedure (e.g. genetic programming) to find an optimal ball.
Jonas Köhler
CC BY-SA 3.0
2016-06-16T13:19:52.727Z
2016-06-16T13:19:52.727Z
Leo
<p>I am searching for the name of / literature to the algorithmic problem as follows:</p>

<blockquote>
  <p>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)| $</p>
</blockquote>

<p>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 <em>Maximum-Enclosing-Disk</em>-Problem. Any information regarding generalizations for $\mathbb{R}^D, D &gt; 2$ or different metrics, would be helpful. </p>

<p>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.</p>

<p>Thank you for your answers.</p>

<p>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.  </p>

CC BY-SA 3.0
2016-06-16T13:26:17.070Z
In general it could be anything, e.g. the space of strings provided with the edit-distance. 

However, even a solution for finite dimensional inner product spaces over the real numbers ($(\mathbb{R}^D, <\cdot, \cdot>),~D< \infty$) would help me a lot. I can find literature for the real euclidean plane. But that would be far too restrictive.
Jonas Köhler
CC BY-SA 3.0
2016-06-16T13:33:46.410Z
Ok. You are right. In this case it would still be very helpful to restrict it to the problem of real vector-spaces with common metrics and arbitrary dimension.

I was considering only "useful" metrics, but I see my fallacy here. Looks as was blindfolded by my domain...
Jonas Köhler
<ds.algorithms><optimization><computational-geometry>
Find the maximum subset contained by a ball of radius R
Jonas Köhler
# Find the maximum subset contained by a ball of radius R

(Asked by: username_0 on 2016-06-16)

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.

**Tags:** ds.algorithms, optimization, computational-geometry
> **Comments:**
> **username_0**: In general it could be anything, e.g. the space of strings provided with the edit-distance.   However, even a solution for finite dimensional inner product spaces over the real numbers ($(\mathbb{R}^D, <\cdot, \cdot>),~D< \infty$) would help me a lot. I can find literature for the real euclidean plane. But that would be far too restrictive.  
> **username_0**: Ok. You are right. In this case it would still be very helpful to restrict it to the problem of real vector-spaces with common metrics and arbitrary dimension.  I was considering only "useful" metrics, but I see my fallacy here. Looks as was blindfolded by my domain...  

---

## 3 answers

### Answer by username_0 on 2016-06-17. Score: 1

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 by username_1 on 2016-06-16. Score: 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 by username_2 on 2016-06-16. Score: 0

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.

> **Comments:**
> **username_0**: But this would be very restrictive. Imagine a square of four points $x_1, \dots, x_4$ in the real plane with side length $\frac{R}{\sqrt{2}}$. Any $R$-ball centered at one of these points would only capture three points, whereas the optimal solution would be taking the center of mass returning 4  as the correct maximum number.  An (intuitive) approximation idea would be taking the sets of $R$-neighbors in $X$ for every $x \in X$ as they are candidate sets and proceed with a classical optimization procedure (e.g. genetic programming) to find an optimal ball.  

---

