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

quasi wrote:
On Tue, 13 Jan 2009 23:55:55 -0500, quasi <quasi@xxxxxxxx> wrote:

On Tue, 13 Jan 2009 23:26:30 -0500, quasi <quasi@xxxxxxxx> wrote:

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.
Well, using Maple, I've verified that f(n) >= n, for 1 <= n <= 100.

Not terribly surprising, since f(n) is most likely of order of
magnitude more than any fixed positive integer power of n.

Ok, I can prove f(n) >= n for all n in N.

More generally, f(n) >= floor((2^n)/(1+5/6*n+1/6*n^3))

(Since f(n) = b(n) >= a(n) -- see below).

A few questions, and a game ...
[...]

I did some searching for packing balls of the same radius in the unit
cube in R^n, and didn't find much for n>3. But there's one
result that's quite appealing:

Suppose 2^n balls of radius 1/2 are packed inside [0, 1]^n , each in its
own "corner" of the hypercube. In the empty space left around the center
of the hypercube, what is the radius of the largest ball that can be
put there, touching all 2^n of the corner balls?

This is the answer I found from:
http://gregegan.customer.netspace.net.au/APPLETS/29/HypercubeNotes.html

near the bottom of the page (credit and (c) to Greg Egan):

<< Now, imagine placing one more n-ball at the center of the original n-cube,
with its radius chosen to be just large enough that it touches every
one of the 2^n other n-balls. For n=2, this central n-ball will be
much smaller than the others, but for n=4 it is the same size.
For n=9 it is twice as big, and hence touches the boundary of the
large n-cube, and for n=10 it extends beyond that n-cube. >>

So, if the edges of the hypercube were made of 1-dimensional wire,
and the 2^n radius 1/2 balls were in place, it seems that
someone living in R^10 could see the larger center ball
sticking out from the "box-shape" formed by the wire frame.

So imagine n = 10^6 ... It seems like it would stick out by a mile,
even for an 8 inch x 8 inch x .... 8 inch "box".

David Bernier
.

Relevant Pages