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!

Improve this question
$\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$
    – Greg Martin
    Commented 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
    Commented 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
    Commented 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
    Commented 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
    Commented Jun 28, 2013 at 2:10

1 Answer 1

Reset to default
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.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .