3 ms·

This is cool, but I'm not sure why it's a hard problem to solve for a computer running through a ton of 5-sided polygons with some basic rules and attempting to

This is cool, but I'm not sure why it's a hard problem to solve for a computer running through a ton of 5-sided polygons with some basic rules and attempting to tessellate them? Is there a reason that approach doesn't work, other than being rather un-romantic as far as discovering cool new things like this goes?

pavpanchekha 11y ago
Yeah, great reasons why it doesn't work—what 5-sided polygons are you going to run through? The hard bit is the side lengths; there are good reasons to think that the angles cannot be too weird. But for example, this pentagon has one side of side length 1 / (sqrt(2) (sqrt(3) - 1)). How long is your exhaustive enumeration going to go until it finds that one? Anyway, it sounds like clever enumeration is exactly what these authors did—but you do have to be clever to find something at all.
- Pyxl101 11y ago
  > 1 / (sqrt(2) (sqrt(3) - 1)) I don't mean in any way to demean their research, but I think your exhaustive search could build up formulas in exactly that form and iterate on them. It starts with a valid pentagon. Then it permutes that pentagon with an evolutionary method by modifying the formula. For example, maybe the lengths it tries are: 1 / 2 1 / sqrt(2) 1 / sqrt(2) * 3 1 / sqrt(2) - 1 1 / sqrt(2) * (3) 1 / sqrt(2) * sqrt(3) It would try both these and many others along the way. 1 / exp(2) ... 2 / sqrt(2) ... Again, not to trivialize, but there are only so formulas made up of a fixed number of terms and operators, and as long as it's easy to check whether a shape is a valid pentagon, and whether it tiles, then I think you could check a considerable number of them. It looks like a number of the pentagon formulas have a few sides with complex lengths, while the others are simple or equal to each other, so you could bias the algorithm to search for those. I'm sure there's way more complexity I'm overlooking, but that's how one might get started.
  - ntoronto 11y ago
    "I'm sure there's way more complexity I'm overlooking, but that's how one might get started." That's how I'd start. There's probably a way to make the search a lot smarter. Here's the part you're overlooking, though: "... there are only so [many] formulas made up of a fixed number of terms and operators..." "So many" = "countably infinite." Paring it down to finitely many would require understanding tantamount to having solved the problem in the first place. [Edit: I can words.]
  - rtpg 11y ago
    This could work for approximations. But if you want the exact value, this might not be super effective, as there are values without closed forms (that is to say, that are not expressible simply with the *-+/ and sqrt/log and other usual operations). So your iteration procedure will probably get to a good approximation, but might not find the "core" expression.
  - gizmo686 11y ago
    In this case, (with the hindsight of knowing the answer), it would probably be easier to enumerate the angles, as they were all rational multiples of pi (with the biggest denominator being 12). Still, that gives a naive 5^144 combinations of angles to test. If you reduce this to proper, reduced fractions this comes down to 5^47 [1]. You can probably improve on this further by requiring that the angles form a (convex) polygon, but I suspect that still leaves you with to many to be practical. [1] http://oeis.org/A005728 http://oeis.org/A005728
- tlarkworthy 11y ago
  The angles don't seem so weird though
- JoshTriplett 11y ago
  I'd be even more curious about the computation used to determine if a given set of sides and angles tessellates, and how long that computation takes. Approaches to enumerate possible expressions don't seem that far-fetched, if the resulting possibilities can be evaluated quickly.
- foota 11y ago
  mind elaborating on why the angles can't be too weird? I thought it was odd that the angles given were all integers.
  - gizmo686 11y ago
    The one thing that the unit of "degrees" has going for it is that it tends to give integer answers (because 360 is so divisible). If you convert them into rotations around a circle, they angles become (1/6, 3/8, 7/24, 1/4, 5/12). (Multyply those by τ=2π to get the angle in radians). EDIT: To your question as to why angles can't be to weird, consider vertices, where the corners of the pentagons meet. Each vertex is composed of three angles, one from each of the three neighboring vertices (although it is not a-priori obvious that a vertex contains only three angles). The sum of these angles (in rotations) must be 1. This means that, heuritstically, you would want as many permutations of the angles as possible to add up to one.
DanBC 11y ago
That approach does work. From the article: "We discovered the tile using using a computer to exhaustively search through a large but finite set of possibilities,” said Casey.
- bradjohnson 11y ago
  Right? I love when people ask "Why don't they do X?" without even bothering to read the damn article. Does the parent think that people just randomly stumbled upon this shape?
nikanj 11y ago
Just going to leave this here https://xkcd.com/793/ https://xkcd.com/793/

pavpanchekha 11y ago

Yeah, great reasons why it doesn't work—what 5-sided polygons are you going to run through? The hard bit is the side lengths; there are good reasons to think that the angles cannot be too weird. But for example, this pentagon has one side of side length 1 / (sqrt(2) (sqrt(3) - 1)). How long is your exhaustive enumeration going to go until it finds that one? Anyway, it sounds like clever enumeration is exactly what these authors did—but you do have to be clever to find something at all.

Pyxl101 11y ago
> 1 / (sqrt(2) (sqrt(3) - 1)) I don't mean in any way to demean their research, but I think your exhaustive search could build up formulas in exactly that form and iterate on them. It starts with a valid pentagon. Then it permutes that pentagon with an evolutionary method by modifying the formula. For example, maybe the lengths it tries are: 1 / 2 1 / sqrt(2) 1 / sqrt(2) * 3 1 / sqrt(2) - 1 1 / sqrt(2) * (3) 1 / sqrt(2) * sqrt(3) It would try both these and many others along the way. 1 / exp(2) ... 2 / sqrt(2) ... Again, not to trivialize, but there are only so formulas made up of a fixed number of terms and operators, and as long as it's easy to check whether a shape is a valid pentagon, and whether it tiles, then I think you could check a considerable number of them. It looks like a number of the pentagon formulas have a few sides with complex lengths, while the others are simple or equal to each other, so you could bias the algorithm to search for those. I'm sure there's way more complexity I'm overlooking, but that's how one might get started.
- ntoronto 11y ago
  "I'm sure there's way more complexity I'm overlooking, but that's how one might get started." That's how I'd start. There's probably a way to make the search a lot smarter. Here's the part you're overlooking, though: "... there are only so [many] formulas made up of a fixed number of terms and operators..." "So many" = "countably infinite." Paring it down to finitely many would require understanding tantamount to having solved the problem in the first place. [Edit: I can words.]
- rtpg 11y ago
  This could work for approximations. But if you want the exact value, this might not be super effective, as there are values without closed forms (that is to say, that are not expressible simply with the *-+/ and sqrt/log and other usual operations). So your iteration procedure will probably get to a good approximation, but might not find the "core" expression.
- gizmo686 11y ago
  In this case, (with the hindsight of knowing the answer), it would probably be easier to enumerate the angles, as they were all rational multiples of pi (with the biggest denominator being 12). Still, that gives a naive 5^144 combinations of angles to test. If you reduce this to proper, reduced fractions this comes down to 5^47 [1]. You can probably improve on this further by requiring that the angles form a (convex) polygon, but I suspect that still leaves you with to many to be practical. [1] http://oeis.org/A005728 http://oeis.org/A005728
tlarkworthy 11y ago
The angles don't seem so weird though
JoshTriplett 11y ago
I'd be even more curious about the computation used to determine if a given set of sides and angles tessellates, and how long that computation takes. Approaches to enumerate possible expressions don't seem that far-fetched, if the resulting possibilities can be evaluated quickly.
foota 11y ago
mind elaborating on why the angles can't be too weird? I thought it was odd that the angles given were all integers.
- gizmo686 11y ago
  The one thing that the unit of "degrees" has going for it is that it tends to give integer answers (because 360 is so divisible). If you convert them into rotations around a circle, they angles become (1/6, 3/8, 7/24, 1/4, 5/12). (Multyply those by τ=2π to get the angle in radians). EDIT: To your question as to why angles can't be to weird, consider vertices, where the corners of the pentagons meet. Each vertex is composed of three angles, one from each of the three neighboring vertices (although it is not a-priori obvious that a vertex contains only three angles). The sum of these angles (in rotations) must be 1. This means that, heuritstically, you would want as many permutations of the angles as possible to add up to one.

DanBC 11y ago

That approach does work. From the article: "We discovered the tile using using a computer to exhaustively search through a large but finite set of possibilities,” said Casey.

bradjohnson 11y ago
Right? I love when people ask "Why don't they do X?" without even bothering to read the damn article. Does the parent think that people just randomly stumbled upon this shape?

nikanj 11y ago

Just going to leave this here https://xkcd.com/793/ https://xkcd.com/793/