Hacker News Reader

Comment by pavpanchekha | Hacker News Reader

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.

View on HN

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

"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.]

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.

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

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.

mind elaborating on why the angles can't be too weird? I thought it was odd that the angles given were all integers.

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.

The angles don't seem so weird though

Reply on news.ycombinator.com