Re: Radius of largest n+1 balls in n-dimensional unit cube?

On Tue, 13 Jan 2009 19:53:41 -0800 (PST), Matt
<matt271829-news@xxxxxxxxxxx> wrote:

On Jan 14, 2:00 am, quasi <qu...@xxxxxxxx> wrote:
On Tue, 13 Jan 2009 17:37:51 -0800 (PST), Matt





<matt271829-n...@xxxxxxxxxxx> wrote:
On Jan 14, 1:17 am, Ross <rmill...@xxxxxxxxxxx> wrote:
On Jan 13, 1:00 pm, Matt <matt271829-n...@xxxxxxxxxxx> wrote:

On Jan 13, 8:35 pm, quasi <qu...@xxxxxxxx> wrote:

On Tue, 13 Jan 2009 12:18:27 -0800 (PST), Golabi Doon

<golabid...@xxxxxxxxx> wrote:
Thank you Quasi! Would you please provide a hint about how I can
derive the formula you proposed? The only piece I understand is that
sqrt(n) is maximal distance between two corners of the cube, but have
no idea how it entered into your formula.

Ok, but please don't top post. Instead, either bottom post or
intersperse portions of your reply after the relevant parts of the
prior message (as I am doing here). That's the standard in sci.math.

For the configuration I described, r can be calculated as follows:

Place a little cube of edge length r in the corner of the unit cube.
Then the distance from the center of the ball in that corner to the
corner vertex is the length of the diagonal of the little cube, which
is r*sqrt(n) (by proportionality to the unit cube).

Then (draw a diagram to see it),

   r + r + r*sqrt(n) = (1/2)*sqrt(n)

which yields

   r = sqrt(n) / (2*(2+sqrt(n)))

On Jan 13, 2:01 pm, quasi <qu...@xxxxxxxx> wrote:
On Tue, 13 Jan 2009 11:19:11 -0800 (PST), Golabi Doon

<golabid...@xxxxxxxxx> wrote:
Hello,

I would appreciate your help or comment about the following problem.
Consider a N dimensional space. If I want to put N+1 balls (all with
the same radius R), within the unit hypercube such that:

1. The balls do not cut through each other
2. One of the balls is at the center of the cube, i.e. at (0.5 , 0.5,
0.5, ...., 0.5)

Then what is the maximum possible R in terms of N? If not easy, a good
approximation will be helpful too.

It seems intuitive that the maximum r for your problem occurs when the
other n balls are in the corners, tangent to the central ball and
tangent to the corner faces. For that configuration,

   r = sqrt(n) / (2*(2+sqrt(n)))

But note, the unit cube in R^n has 2^n corners, so you could just as
easily have (2^n)+1 balls with the same radius as above, rather than
only n+1.

But for n > 4, 4*r > 1, so does that mean they wouldn't actually all
fit?

The radius is always <1/2, so the central ball always fits in the
cube.  There is nothing
special about r>1/4.

I'm not doubting that the central ball fits in the cube. I'm querying
Quasi's claim that immediately preceded my reply -- namely that, in
the configuration he describes, you could "easily have (2^n)+1 balls
with the same radius" (i.e. a ball at every corner).

And it was a good query.

I take back the claim.

As you point out, since 4r > 1 when n > 4, you can't have balls with
radius r, configured as I described, in 2 adjacent corners.

Thus, for n > 4, you can't have 2^n + 1 balls in that configuration,
with that radius.

As to how many you can have -- good question -- I'll play with it.

I was thinking about graphs before, but I guess it may be simpler to
think of strings of n symbols, each symbol being either 1 or 0 (say).
Then we want as many strings as possible such that any two differ in
at least m places, where m = ceil(n/4) (according to what I got
earlier when I was playing).

Yes, that's how I was analyzing it. No geometry -- purely
combinatorial.

This must be a well-studied problem.

Yes, very likely.

In any case, letting f(n) = the maximum number of balls with radius

 r = sqrt(n) / (2*(2+sqrt(n)))

which can be placed, without overlapping, in the corners of a unit
cube in R^n, then

f(1) = 2
f(2) = 4
f(3) = 8
f(4) = 16
f(5) >= 16
f(6) >= 32
f(7) >= 58

where the inequalities above represent achievable values (found via
Maple), and hence are only lower bounds.

It's seems almost a certainty that f(n) >= n for all n in N, which
would satisfy your original requirements. But R^n often has some
surprises in store when n > 3, so without a proof, or an actual
construction, there is still a tiny bit of worry.

quasi
.

Relevant Pages
Loading