Author 
Topic: Pseudotessellation (Read 2603 times) 

ecks
Newbie
Posts: 2


Pseudotessellation
« on: May 24^{th}, 2009, 3:26pm » 
Quote Modify

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 nonrepeating one, a la Penrose tiling). Is there a nonzero 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.


IP Logged 



towr
wu::riddles Moderator Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730


Re: Pseudotessellation
« Reply #1 on: May 25^{th}, 2009, 12:03am » 
Quote Modify

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).


IP Logged 
Wikipedia, Google, Mathworld, Integer sequence DB



ecks
Newbie
Posts: 2


Re: Pseudotessellation
« Reply #2 on: May 25^{th}, 2009, 11:45am » 
Quote Modify

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.


IP Logged 



towr
wu::riddles Moderator Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730


Re: Pseudotessellation
« Reply #3 on: May 25^{th}, 2009, 1:38pm » 
Quote Modify

on May 25^{th}, 2009, 11:45am, ecks wrote: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%. 
 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.


IP Logged 
Wikipedia, Google, Mathworld, Integer sequence DB



brac37
Newbie
Gender:
Posts: 23


Re: Pseudotessellation
« Reply #4 on: May 26^{th}, 2009, 8:18am » 
Quote Modify

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.


IP Logged 



Aryabhatta
Uberpuzzler
Gender:
Posts: 1321


Re: Pseudotessellation
« Reply #5 on: May 26^{th}, 2009, 7:21pm » 
Quote Modify

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?


IP Logged 



Obob
Senior Riddler
Gender:
Posts: 489


Re: Pseudotessellation
« Reply #6 on: May 26^{th}, 2009, 11:54pm » 
Quote Modify

The notion of percentage covered is not welldefined 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>. 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^{2}/G. It is compact, and it inherits a notion of "area" from R^2. (Formally, the volume form on R^2 is Ginvariant, so descends to the quotient) Furthermore, the pattern on R^{2} gives us a pattern on the quotient R^{2}/G. Now we just ask what fraction of R^{2}/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^{2}/G is compact.

« Last Edit: May 26^{th}, 2009, 11:56pm by Obob » 
IP Logged 



Aryabhatta
Uberpuzzler
Gender:
Posts: 1321


Re: Pseudotessellation
« Reply #7 on: Jun 16^{th}, 2009, 2:46pm » 
Quote Modify

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


IP Logged 



