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

In article <8e3rm41gejmfbgg534h7co1vi20dnu46e0@xxxxxxx>,
quasi <quasi@xxxxxxxx> 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))

The radius of each sphere is r, so r sqrt(n) is the distance from the
corner of the cube to the center each of the corner spheres. 2r is
the distance from the center of each corner sphere to the center of
the center sphere. Since the distance from the corner to the center
of the cube is sqrt(n)/2, we get

r (2 + sqrt(n)) = sqrt(n)/2 [1]

sqrt(n)/2
r = ----------- [2]
2 + sqrt(n)

This is the result derived above.

Let's enumerate the 2^n corners of the cube by binary integers, with
each bit representing one axis. The distance between the centers of
two corner spheres whose corners differ by d bits (Hamming distance
of d) is 4r sqrt(d/n). So that the euclidean distance between the
centers is at least 2r, we need to have 4r sqrt(d/n) >= 2r; that is,
d >= n/4.

If we cover the corners of the cube with balls of Hamming radius d-1,
where the center of each ball is outside of all other balls, then
each center is at least a Hamming distance of d from the others. We
can estimate the number of corners in a ball of Hamming radius d-1.

The number of corners up to d-1 bits from a given corner is

C(n,d-1) + C(n,d-2) + ... + C(n,1) + C(n,0)

d d(d-1)
= ----- C(n,d) + -------------- C(n,d) + ...
n-d+1 (n-d+1)(n-d+2)

d d 2
<= --- C(n,d) + ( --- ) C(n,d) + ...
n-d n-d

d
= ---- C(n,d)
n-2d

~ 1/2 C(n,d) [3]

when d ~ n/4. Using Stirling's approximation, we get

2 4 n
1/2 C(n,d) ~ sqrt( ----- ) ( ------- ) [4]
3pi n 3^(3/4)

when d ~ n/4. To cover all 2^n corners, we need at least

2^n/(C(n,d-1) + C(n,d-2) + ... + C(n,1) + C(n,0)) [5]

balls of Hamming radius d-1. Because the balls may overlap, we may
need more, but this is a minimum. Therefore, we can find at least
this many corners so that the spheres in those corners are the
requisite distance apart.

Using [3], [4], and [5], we get that this minimum is asymptotic to

3pi n 3^(3/4) n
sqrt( ----- ) ( ------- ) [6]
2 2

Using [5] and [6], it is possible to show that the ceiling of [5]
is always greater than n. In fact, if we try to find an n so that
[6] is equal to n, we get

n = LambertW( 3/2 pi log(4/3^(3/2)) ) / log(4/3^(3/2))

However, since 3/2 pi log(4/3^(3/2)) < -exp(-1), there is no such n.

Thus, in R^n, there are always at least n disjoint corner spheres of
the euclidean radius given in [2] inside the cube of side 1 not
overlapping the central sphere of the same radius.

However, the minimum given in [5] is much smaller than the estimate
floor((2^n)/(1+5/6*n+1/6*n^3)) you give. You never show why this
estimate holds.

Rob Johnson <rob@xxxxxxxxxxxxxx>
take out the trash before replying
to view any ASCII art, display article in a monospaced font
.

Relevant Pages

  • Re: Radius of largest n+1 balls in n-dimensional unit cube?
    ... sqrtis maximal distance between two corners of the cube, ... Then the distance from the center of the ball in that corner to the ... If I want to put N+1 balls (all with ... the same radius R), within the unit hypercube such that: ...
    (sci.math)
  • Re: Radius of largest n+1 balls in n-dimensional unit cube?
    ... sqrtis maximal distance between two corners of the cube, ... Then the distance from the center of the ball in that corner to the ... If I want to put N+1 balls (all with ... the same radius R), within the unit hypercube such that: ...
    (sci.math)
  • Re: Radius of largest n+1 balls in n-dimensional unit cube?
    ... sqrtis maximal distance between two corners of the cube, ... Then the distance from the center of the ball in that corner to the ... If I want to put N+1 balls (all with ... the same radius R), within the unit hypercube such that: ...
    (sci.math)
  • Re: Radius of largest n+1 balls in n-dimensional unit cube?
    ... Place a little cube of edge length r in the corner of the unit cube. ... the same radius R), within the unit hypercube such that: ... The balls do not cut through each other ... own "corner" of the hypercube. ...
    (sci.math)
  • Re: Radius of largest n+1 balls in n-dimensional unit cube?
    ... 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 ... the same radius R), within the unit hypercube such that: ... The balls do not cut through each other ...
    (sci.math)