wu :: forums - Print Page


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

        riddles >> hard >> Pseudo-tessellation
        
(Message started by: ecks on May 24^th, 2009, 3:26pm)

Title: Pseudo-tessellation
Post by ecks on May 24^th, 2009, 3:26pm

Suppose you have an infinite plane and an infinite number of congruent convex polygons of finite area. You are given the task of placing these shapes onto the plane in such a way that they cover the largest percentage of the plane's area as possible without overlapping (this might be a repeating sequence, or perhaps a non-repeating one, a la Penrose tiling). Is there a non-zero lower bound to this percentage covered by the shape? If so, what is it, and what shape has it?

The first question is trivially a "yes", but although I can only guess the answer to the second one (a circle?), I haven't been able to come up with anything.

Title: Re: Pseudo-tessellation
Post by towr on May 25^th, 2009, 12:03am

I think that using a bounding rectangle, you get 50% coverage (worst case is a triangle; which of course would give you 100% coverage if you tile it in a normal way).

Title: Re: Pseudo-tessellation
Post by ecks on May 25^th, 2009, 11:45am

I'm not sure I get what you mean. A minimum bounding rectangle might, when tessellated, give it a poor coverage, but certainly there are better ways to tile the plane (as you pointed out with the triangle). That might be the start of an argument, but I'm not sure that that proves that it could be 50%. It might be done by finding a shape that can't tile any better than when arranged in a grid with its MBR and coves minimal area of that rectangle.

It almost feels like an exhaustion argument would be needed to prove it.

Title: Re: Pseudo-tessellation
Post by towr on May 25^th, 2009, 1:38pm

on 05/25/09 at 11:45:55, ecks wrote:

Well, if my hypothesis is right, then you can always do at least as well as 50%, so 50% is a lower bound. It may however not be a tight lower bound (i.e. that it's the best you can do in the worst case).
It's a start at least. And maybe it invites some of the other puzzlers here to improve on the bound ;)

Quote:

It might be done by finding a shape that can't tile any better than when arranged in a grid with its MBR and coves minimal area of that rectangle.

That would be necessary to prove it's a tight bound yes, but to be honest I have my doubts there is such a tile. You can always do at least as well, and often better with a (degenerated*) hexagonal tiling.

*) Obviously, because a rectangle is a degenerated hexagonal, where two opposite sides have length 0.

Title: Re: Pseudo-tessellation
Post by brac37 on May 26^th, 2009, 8:18am

I wonder whether the regular pentagon can reach the honeycomb bound of the circle.

You can tile quadrilaterals even without mirroring. Saying that, you can ask the question with or without allowing mirroring. Without rotating, I think that the answer to the questions is 66 2/3 percent.

Title: Re: Pseudo-tessellation
Post by Aryabhatta on May 26^th, 2009, 7:21pm

Is there any rigorous definition of "percentage" area covered by a tiling?

It does not seem obvious that all (reasonable) alternative definitions of this "percentage" would lead to the same answer.

Am I missing something obvious?

Title: Re: Pseudo-tessellation
Post by Obob on May 26^th, 2009, 11:54pm

The notion of percentage covered is not well-defined in general, but should be if the pattern repeats. One reasonable definition is that the percentage covered is the limit of the fraction of an n x n box which is covered, as n->http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/infty.gif. Of course you could also use a circle of radius n instead of squares, or do any number of other things. For repeating patterns, these should all give the same answer. The trickiest part in making this rigorous is probably explaining precisely what one means by a "repeating pattern." If you do this, then you can choose a "fundamental domain" for the symmetry group of the plane describing the repeating nature of the pattern. The portion of one fundamental domain covered by your pattern is then the percentage coverage for the pattern.

We can get away without worrying about constructing a fundamental domain as follows: If we have a repeating pattern, let G be the group of symmetries of the pattern. We can form the quotient manifold R²/G. It is compact, and it inherits a notion of "area" from R^2. (Formally, the volume form on R^2 is G-invariant, so descends to the quotient) Furthermore, the pattern on R² gives us a pattern on the quotient R²/G. Now we just ask what fraction of R²/G is covered by the pattern.

For nonrepeating patterns, the limit might exist or it might not, and it will generally depend on the way in which you choose to define percentage covered. Moreover, there isn't a good solution to the problem. Essentially what we are trying to do is ascribe to any subset of the plane a number between 0 and 1, which corresponds to the intuitive "percentage covered." Choosing a number between 0 and 1 for each subset of the plane basically means we are choosing a probability distribution on the plane. This distribution should be translation invariant, since the percentage covered by a pattern should be the same as the percentage covered by its translate. But there aren't any translation invariant probability distributions on the plane. Topologically, the plane would have to be compact in order to have such a probability distribution. In the case of repeating patterns, we got around this, since R²/G is compact.

Title: Re: Pseudo-tessellation
Post by Aryabhatta on Jun 16^th, 2009, 2:46pm

Sorry, I missed your reply Obob. I would need to do some brushing up to understand completely what you wrote. Thanks!