10
$\begingroup$

Let $R>0$ be given and let $H^n$ be the unit hypercube in $\mathbb{R}^n$. The problem I am facing is to find the maximum number of vertices of $H^n$ which can be covered by a closed $n$-dimensional ball of radius $R$.

I would greatly appreciate any references to literature or ideas on how to approach the problem. I strongly suspect that a solution for any $R$ comes from placing the center of the ball at $(\frac{1}{2},\frac{1}{2},\ldots,\frac{1}{2},0,\ldots,0)$ with the number of nonzero coordinates being $\lfloor 4R^2 \rfloor=\lfloor D^2 \rfloor $, where $D$ is the diameter (for $D \leq n$).

Any references or ideas are welcome.

Thanks!

$\endgroup$
7
  • 1
    $\begingroup$ That seems like a good guess to me. You could try using the fact that any set of more than $2^k$ vertices of $H^n$ cannot be contained in a $k$-dimensional affine subspace of $\mathbb R^n$. $\endgroup$ May 9, 2013 at 0:52
  • $\begingroup$ This is not always true. Already if n=2 (we have a square), then if R is a little less than $\sqrt(2)/2$, then the best we can do is to cover 3 vertices. $\endgroup$
    – domotorp
    Jun 25, 2013 at 15:12
  • $\begingroup$ @domotorp Indeed, it is not always true. However, if one can cover 3 vertices then one can cover the whole square. I believe the conjecture first breaks down at dimension 16 $\endgroup$
    – user21277
    Jun 26, 2013 at 19:42
  • $\begingroup$ I think you are mistaken, in my example with the given radius we can cover 3 vertices but not the whole square. $\endgroup$
    – domotorp
    Jun 27, 2013 at 15:14
  • $\begingroup$ @domotorp Consider 3 vertices of a square. These form an isosceles right triangle. The circumcenter of this triangle is the midpoint of the hypotenuse, which is also the center of the square. $\endgroup$
    – user21277
    Jun 28, 2013 at 2:10

1 Answer 1

2
$\begingroup$

Sometimes it is better to place the ball "in the corner". For example:

Let $n=8$ and $R=\sqrt{\frac{7}{8}}$. Then the ball with center $(\frac{1}{8}, \frac{1}{8}, \dots, \frac{1}{8})$ and radius $R$ covers exactly $9$ vertices (those with at most one coordinate equal to $1$), but a ball with radius $R$ cannot cover a $4$-dimensional unit hypercube, which requires radius at least $1$.

There is even no upper bound on the number of points a ball with radius $1$ can cover, provided the dimension is not bounded. Generalizing previous construction, a ball with center $(\frac{1}{n}, \frac{1}{n}, \dots, \frac{1}{n})$ and radius $\sqrt{\frac{n-1}{n}}$ covers $n+1$ vertices of the $n$-dimensional hypercube. As user21277 points out, for $n=16$ this is better than placing the ball in the center of a $4$-dimensional face.

In general, for $n>2i$, a ball with center $(\frac{i}{n}, \frac{i}{n}, \dots, \frac{i}{n})$ and radius $\sqrt{\frac{i(n-i)}{n}}$ covers ${n \choose i} + {n \choose i-1} + \cdots +{n \choose 0}$ vertices: those with at most $i$ coordinates equal to $1$. A ball with the same radius cannot cover all $2^{4i}$ vertices of a $4i$-dimensional unit hypercube.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.