Author |
Topic: Pseudo-tessellation (Read 2634 times) |
|
ecks
Newbie
Posts: 2
|
 |
Pseudo-tessellation
« on: May 24th, 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 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.
|
|
 IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender: 
Posts: 13730
|
|
Re: Pseudo-tessellation
« Reply #1 on: May 25th, 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: Pseudo-tessellation
« Reply #2 on: May 25th, 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: Pseudo-tessellation
« Reply #3 on: May 25th, 2009, 1:38pm » |
Quote Modify
|
on May 25th, 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: Pseudo-tessellation
« Reply #4 on: May 26th, 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: Pseudo-tessellation
« Reply #5 on: May 26th, 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: Pseudo-tessellation
« Reply #6 on: May 26th, 2009, 11:54pm » |
Quote Modify
|
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-> . 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 R2/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 R2 gives us a pattern on the quotient R2/G. Now we just ask what fraction of R2/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 R2/G is compact.
|
| « Last Edit: May 26th, 2009, 11:56pm by Obob » |
IP Logged |
|
|
|
Aryabhatta
Uberpuzzler
Gender:
Posts: 1321
|
|
Re: Pseudo-tessellation
« Reply #7 on: Jun 16th, 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 |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print