wu :: forums « wu :: forums - Pseudo-tessellation » Welcome, Guest. Please Login or Register. Jul 5th, 2022, 9:04pm RIDDLES SITE WRITE MATH! Home Help Search Members Login Register
 wu :: forums    riddles    hard (Moderators: SMQ, towr, Eigenray, Grimbal, william wu, ThudnBlunder, Icarus)    Pseudo-tessellation « Previous topic | Next topic »
 Pages: 1 Reply Notify of replies Send Topic Print
 Author Topic: Pseudo-tessellation  (Read 2610 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
 Pages: 1 Reply Notify of replies Send Topic Print

 Forum Jump: ----------------------------- riddles -----------------------------  - easy   - medium => hard   - what am i   - what happened   - microsoft   - cs   - putnam exam (pure math)   - suggestions, help, and FAQ   - general problem-solving / chatting / whatever ----------------------------- general -----------------------------  - guestbook   - truth   - complex analysis   - wanted   - psychology   - chinese « Previous topic | Next topic »