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

        riddles >> hard >> Mutually Touching Objects
        
(Message started by: Barukh on Jan 23rd, 2004, 9:38am)
Title: Mutually Touching Objects
Post by Barukh on Jan 23rd, 2004, 9:38am
1. What is the maximum number of convex polygons in the plane, non-overlapping and such that any pair of them have a common boundary of positive length?

2. What is the maximum number of convex polyhedra in the 3D space, non-overlapping and such that any pair of them have a common boundary of positive area?
Title: Re: Mutually Touching Objects
Post by towr on Jan 23rd, 2004, 10:20am

on 01/23/04 at 09:38:02, Barukh wrote:
1. What is the maximum number of convex polygons, non-overlapping and such that any pair of them have a common boundary of positive length?
infinitely many, in infinite dimensional space.. :P (Or even in just 3D space actually..)
::[hide]for 2D I can get at least 4[/hide]::


Quote:
2. What is the maximum number of convex polyhedra, non-overlapping and such that any pair of them have a common boundary of positive area?
Probably also infinite for nD (n>3) space ;D
Title: Re: Mutually Touching Objects
Post by Barukh on Jan 24th, 2004, 12:28am
OK, I forgot to mention that the objects should be considered in corresponding dimensions  ;) - I modified the problem statement.
Title: Re: Mutually Touching Objects
Post by rmsgrey on Jan 24th, 2004, 3:44am
1)::[hide]The four-colour theorem states that for any arrangement of connected regions in the plane, they can be coloured using four colours such that no adjacent regions share a colour, so no subset of five or more regions, be they convex or otherwise can touch each other. Finding a set of four convex polygons is easy.[/hide]::

2) I've only managed a lower bound on this one ::[hide]5 - four arranged tetrahedrally with a little one in the middle[/hide]:: though for non-convex, the answer is of course that you can get arbitrarily many.

[e]Someday I'll get the hang on hide tags...[/e]
Title: Re: Mutually Touching Objects
Post by rmsgrey on Jan 24th, 2004, 4:21am
2) Further thought reminds me that this is a general case of Cigarettes Max Clique (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi?board=riddles_hard;action=display;num=1027804466) - one of the long-term unsolved problems (currently stuck at 7 for long enough identical cylinders; 8 for varying lengths)

[e]fixed link[/e]
[e2]re-fixed link[/e2]
Title: Re: Mutually Touching Objects
Post by Barukh on Jan 25th, 2004, 6:46am
Good observations, rmsgrey  :D! Despite some similiarity to the mentioned problem, the answer is completely different. In fact, [hide]it's much much bigger[/hide]. Remember: there's no resitriction on the shapes of polyhedra.
Title: Re: Mutually Touching Objects
Post by rmsgrey on Jan 25th, 2004, 10:32am
There is a pretty big restriction on the shapes of polyhedra - they're required to be convex - without which, there is no upper bound.

I forgot to say that, while the cigarettes problem is a special case (and currently stalled without proof), the general case may well be easier to solve.
Title: Re: Mutually Touching Objects
Post by Barukh on Jan 25th, 2004, 10:53am

on 01/25/04 at 10:32:14, rmsgrey wrote:
There is a pretty big restriction on the shapes of polyhedra - they're required to be convex - without which, there is no upper bound.

Well, what I meant: they don't need to have the same shape, and the shape mustn't be cylindrical.
Title: Re: Mutually Touching Objects
Post by towr on Jan 25th, 2004, 11:15am
There is another difference with the cigarette case, the objects mustn't only touch, but must share a non-zero area boundary (as is stipulated in the puzzle) This pretty much rules out cylinders for consideration..
Title: Re: Mutually Touching Objects
Post by rmsgrey on Jan 25th, 2004, 4:05pm
But it's not hard to modify cylinders to provide a non-zero area in contact without sacrificing their convexity - just replace them with n-gon prisms for some large n
Title: Re: Mutually Touching Objects
Post by SWF on Jan 27th, 2004, 6:49pm
An infinite number of polyhedra can fit condition 2.  I already drew one picture for the riddles forum today, and don't feel like making another one today. Perhaps there is an easier to describe method, but my idea is basically to start with polyhedron number 1 as a large flat block, and cut with a plane to remove a thin wedge. Call that wedge polyhedron 2 and put back in place.  Keep cutting with new planes at strategic locations so it cuts all the previous shapes, remove the new thin wedge (containing pieces from each of the pre-existing polyhedra) and replace by a single polyhedron and repeat.  The cut must be done correctly so it does not ruin the other polyhedra all touching one another.

There is a systematic way of doing this, and cutting a convex polyhedron with a plane always leaves convex polyhedra.  Maybe I will try to draw it and more clearly explain tomorrow.
Title: Re: Mutually Touching Objects
Post by John_Gaughan on Jan 28th, 2004, 5:49am

on 01/24/04 at 03:44:58, rmsgrey wrote:
1)::[hide]The four-colour theorem states that for any arrangement of connected regions in the plane, they can be coloured using four colours such that no adjacent regions share a colour, so no subset of five or more regions, be they convex or otherwise can touch each other. Finding a set of four convex polygons is easy.[/hide]::

I thought the problem was restricted to polygons touching along a boundary with positive length, so corners don't count. The four-color theorem implies corners, or boundaries of zero length.
Title: Re: Mutually Touching Objects
Post by Quetzycoatl on Jan 28th, 2004, 10:54am

on 01/28/04 at 05:49:53, John_Gaughan wrote:
I thought the problem was restricted to polygons touching along a boundary with positive length, so corners don't count. The four-color theorem implies corners, or boundaries of zero length.


Actually I think it excludes 0 length boundaries. Anyway here is an example of 4 convex polygons sharing non-zero length positive boundaries.
Title: Re: Mutually Touching Objects
Post by John_Gaughan on Jan 28th, 2004, 12:12pm
Thank you for the image, I don't know why I didn't think of that. I'm a little slower than usual today ;-)
Title: Re: Mutually Touching Objects
Post by Icarus on Jan 28th, 2004, 3:13pm
And Quetzycoatl is correct about the 4-color theorem. It only counts regions as adjacent if they share a border of positive length. If you counted touching only at a single point, maps requiring an arbitrary number N of colors are easy to draw: choose a point and draw N distinct rays out from it. This divides the plane into N regions all of which touch at the common point.
Title: Re: Mutually Touching Objects
Post by Barukh on Jan 29th, 2004, 11:47pm

on 01/27/04 at 18:49:29, SWF wrote:
An infinite number of polyhedra can fit condition 2...

Bravo, SWF, that's right! Just to make it more clear: how many faces the polyhedron #N has in your construction?
Title: Re: Mutually Touching Objects
Post by grimbal on Apr 29th, 2004, 8:48am
I seem to remember there is a solution with an infinite number of polhedras all identical.  They look like a 3d parabola approximated with flat faces.

PS: I have given it another thought tonight, and what I was thinking of does not work.  Sorry.


Powered by YaBB 1 Gold - SP 1.4!
Forum software copyright © 2000-2004 Yet another Bulletin Board