wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> hard >> Sweeping a cube
        
(Message started by: JocK on Dec 7^th, 2004, 10:44am)

Title: Sweeping a cube
Post by JocK on Dec 7^th, 2004, 10:44am

What is the largest volume that fits inside a unit cube in any orientation, and that can be moved around inside this cube so as to sweep it completely?

Title: Re: Sweeping a cube
Post by Barukh on Dec 9^th, 2004, 1:55am

Oh, that seems tough... >:(

To avoid mis-interpretations: "can freely rotate" means "no 2 points of the body are more than a unit length apart"?

Title: Re: Sweeping a cube
Post by Barukh on Dec 9^th, 2004, 5:54am

Here is one idea (assuming my interpretation of “freely rotate” is correct).

Take any figure F that satisfies Sweeping a Square (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi?board=riddles_hard;action=display;num=1102254108). Let the area of F be S. If we dilate F by a factor of k < 1, we get a similar figure F’. In it, every 2 points are at the distance no more than k. The area of F’ is Sk².

Now, on F’ as a base, build a right generalized cylinder (http://mathworld.wolfram.com/Cylinder.html) of height h. If h² + k² [le] 1, no two points in this solid will be more than a unit apart. So, we may achieve the volume of Sk²[sqrt](1-k²). This reaches the maximum 2S/[sqrt]27.

Taking S = 0.6866… (the best known so far) gives 0.264…

I will try to visualize this.

Title: Re: Sweeping a cube
Post by JocK on Dec 9^th, 2004, 12:53pm

on 12/09/04 at 01:55:38, Barukh wrote:

Oh, that seems tough... >:(

C'mon Barukh, a piece of cake for u! (you have solved the 2D case already and I won't bother you with the 4D case... ;) )

on 12/09/04 at 01:55:38, Barukh wrote:

To avoid mis-interpretations: "can freely rotate" means "no 2 points of the body are more than a unit length apart"?

Correct. I will change the wording in the riddle from 'freely rotate inside a unit cube' into: 'can be placed inside a unit cube in any orientation'.

Title: Re: Sweeping a cube
Post by JocK on Dec 9^th, 2004, 1:55pm

on 12/09/04 at 05:54:12, Barukh wrote:

That's a start! :)

Would you have applied the same methodology to find a solution to 2D problem Sweeping a Square (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi?board=riddles_hard;action=display;num=1102254108) given that the 1D problem is trivially solved by a line segment of unit lenth, you would have ended up with a square with unit diagonal and area 1/2. Not bad for a first guess, but not optimal... ;)

Title: Re: Sweeping a cube
Post by Barukh on Dec 10^th, 2004, 11:04am

on 12/09/04 at 12:53:22, JocK wrote:

C'mon Barukh, a piece of cake for u! (you have solved the 2D case already...

You give me too much credit - after all, it was SWF's idea.

Quote:

...and I won't bother you with the 4D case... ;) )

Do you promise? ;)

Title: Re: Sweeping a cube
Post by JocK on Dec 11^th, 2004, 7:33pm

on 12/10/04 at 11:04:10, Barukh wrote:

Do you promise? ;)

Considering various spatial dimensions N = 1, 2, 3, ... might actually help. Reasonable target values for the volume fraction in various dimensions can be defined as follows:

A (hyper)cube with unit diagonal (volume N^-N/2) consitutes a lower bound, and a (hyper)sphere with unit diameter (volume ([sqrt][pi] / 2)^N/Gamma(1 + N/2) ) an upper bound to the solution of the (hyper)cube sweeping problem.

N low.bound upp.bound

1 - - - 1.000 - - - 1.000
2 - - - 0.500 - - - 0.785
3 - - - 0.192 - - - 0.524
4 - - - 0.063 - - - 0.308
5 - - - 0.018 - - - 0.164

The midpoint between this upper bound and this lower bound represents a volume fraction that you should be able to reach or exceed... (at least for all dimensions up to N=5).

Good luck!

Title: Re: Sweeping a cube
Post by Barukh on Dec 12^th, 2004, 1:02am

on 12/11/04 at 19:33:11, JocK wrote:

A (hyper)cube with unit diagonal (volume N^-N/2) consitutes a lower bound, and a (hyper)sphere with unit diameter (volume ([sqrt][pi] / 2)^N/Gamma(1 + N/2) ) an upper bound to the solution of the (hyper)cube sweeping problem.

N low.bound upp.bound

1 - - - 1.000 - - - 1.000
2 - - - 0.500 - - - 0.785
3 - - - 0.192 - - - 0.524
4 - - - 0.063 - - - 0.308
5 - - - 0.018 - - - 0.164

The midpoint between this upper bound and this lower bound represents a volume fraction that you should be able to reach or exceed... (at least for all dimensions up to N=5).

Hmm, that's interesting... For n=2, we get the SWF's proposed solution.

But I don't see why this should be necessarily true for higher dimensions? Probably, my imagination deceives me... :(

Title: Re: Sweeping a cube
Post by Barukh on Feb 19^th, 2005, 5:21am

Is this thread dead? I am still not able to find something better...

More than 2 months have passed since the last post. Maybe, a hint is relevant?

Title: Re: Sweeping a cube
Post by JocK on Feb 19^th, 2005, 1:35pm

on 02/19/05 at 05:21:01, Barukh wrote:

Maybe, a hint is relevant?

OK -- at the danger of giving too much away -- here is a 2nd hint (the first hint being that one should strive for volumes of at least 0.358..):

Think about an octant of a sphere with unit radius. Such a body fits snuggly in the corner of cube, and has a volume as large as 0.524. However, some points on this octant are further than a unit distance apart. So you have to cut off some part(s)...