At the summer school earlier this year, we had two or three projects on aggregation systems and tilings. We’ve now gotten around to writing up some of the overview, but much work remains to be done on the theory and practice of tilings-based cellular automata. The purpose of this memo is to give one more eminently familiar example, the “Pattern Blocks”, and then to explain how this example fits into the future directions plan.
The pattern blocks are a set of six polygons, three regular, two parallelograms, and an odd half-hexagon. As educational implements they’ve been around for over a half-century now, and they’re usually found in the same distinctive, primary colors:
Out[]=
,
,
,
,
,
Here we’ve extracted a nice helper function from the blog post click-to-copy, “FixGraphicsScale”, which insures that each separate image has matching unit edge-lengths. Perhaps this is too much a detail, but in case it helps to know, the half hexagon has a long “double edge” containing an extra midpoint vertex. With this artifice, we can define a simple-but-comprehensive edge-to-edge join rule for the tiles, which results in 46 unique pair configurations modulo rotation and reflection symmetry. They can be generated by combining a new “Canonicalizer” function with more of the Blog’s click-to-copy cloud functions:
Out[]=
But the graph drawing algorithm doesn’t detect collisions of the vertex shape functions, so we need to re-space the initials manually using GraphEmbedding:
Out[]=
We can easily take the calculation to the next level, where we find 1397 unique triples (again after canonicalization by rotation and reflections):
In[]:=
pbG2=Module{inits,g1},inits=[tiles,edges,#]&/@tiles;g1=GraphFlattenReapNest[PatternBlockCanonicalSignature],inits,2[[2]];
In[]:=
Length/@ResourceFunction["VertexStratify"][pbG2]
Out[]=
{6,46,1397}
The number 1397 isn’t too many to inspect, but that many polygons do not fit well in a community post. Here’s a random sampling of 50 instead:
Out[]=
Unfortunately, as is often the case, this one random sample fails to hit the 5% chance of showing the two special examples that already have holes after adding only three tiles:
Out[]=
,
Of course, these holes can be filled easily by a green triangle after only one step. If we add tiles randomly for one hundred steps (which can be done with minimal effort, again by copy-and-pasting from the blog), then we end up with some truly strange holes and coincidences, many of which can not be filed given our constrained set of only six tiles:
In[]:=
Module{unit,init,res,steps=100,ct=0},SeedRandom[1234];init=[tiles,Map[Range,Length@@@tiles],Last@tiles];Monitorres=NestWhilect++;[#]&,init,!FailureQ[#]&,1,steps,ct;rand=res;[20]@DepictPatternBlocks[res]
Out[]=
Taking a closer look at the data, we find that two holes have been identified:
In[]:=
Functionbound,[40]@DepictPatternBlocks[Select[rand["Tiling"],IntersectingQ[Round[100bound[[1]]],Round[100#[[1]]]]&]][rand["Boundary"][#]]&/@{4,7}
Out[]=
,
Also, a third potential-closure has escaped the algorithm’s ledger of holes:
The calculations are not being carried out at infinite precision, so this bad behavior probably boils down to a rounding error made somewhere near the lowest level of the algorithm. Before labeling successes and failures, let’s first verify that these three configurations all have holes at infinite precision.
For the next hole, we can write out the sequence of edge vectors and Fold the path:
It ends with a zero for its x-coordinate, indicating co-linearity. And again, the odd intersection happens by adding or subtracting integers and irrationals on the y-coordinate.
How about the third example? It looks like a hole, but can we prove that? The same tactic of lining up the edge vectors will work again, and we find out indeed it is a hole:
So what happened here? Why did the algorithm fail? With so many moving parts in total, it’s not eaasy to say exactly, but we can at least look closer at the apparent failure point:
Something is apparently very wrong, because even the numerical test says that the points are co-linear:
Although the problem could be somewhere in the tiling iterator, more likely it’s happening with the precision handling of PlanarPolygonFragmentation. This submission was initially tested on relatively well-behaved infinite precision examples, and it still needs another round of development focused on improving its behavior for inputs with arbitrary numerical precision.
While we’re here we might as well start a triage by extracting the case details:
Indeed, PlanarPolygonFragmentation fails to notice the point-like intersection and returns only one component under the “True” key:
Just for the sake of thoroughness, let’s take a closer look at the other two point-like intersections:
The holes are registered correctly under “True” key here:
Out[]//InputForm=
{Polygon[{{{-2.5, -2.5980762113533156}, {-2., -1.732050807568877}, {-2.5,
-0.8660254037844384}, {-2.5, -0.8660254037844383}, {-1.9999999999999998,
-1.732050807568877}, {-2.4999999999999996, -2.5980762113533156}},
{{-3.2320508075688776, -2.598076211353315}, {-3.232050807568876,
-2.598076211353316}, {-3.2320508075688794, -2.598076211353316}}}],
MeshRegion[{{6.866025403784436, -2.5}, {7.732050807568875, -3.}}, {Line[{{1, 2}}]}]}
-0.8660254037844384}, {-2.5, -0.8660254037844383}, {-1.9999999999999998,
-1.732050807568877}, {-2.4999999999999996, -2.5980762113533156}},
{{-3.2320508075688776, -2.598076211353315}, {-3.232050807568876,
-2.598076211353316}, {-3.2320508075688794, -2.598076211353316}}}],
MeshRegion[{{6.866025403784436, -2.5}, {7.732050807568875, -3.}}, {Line[{{1, 2}}]}]}
Perhaps what’s most startling here is not the failure to notice a point-edge intersection, but rather the tendency of RegionIntersection to use wildly different output forms, regardless of how similar inputs are.
The obvious solution to all these problems is just to do the calculations at infinite precision. That is not presently possible with either PlanarPolygonFragmentation or built-in system functions. Unexpected difficulties related to the undecidability of zero-testing need to be addressed in subsequent revisions, which are still unplanned as of this writing.
It’s not known whether PlanarPolygonFragmentation will go on to a second round of development, but if it does, the blog’s “random pentagon” example along with these “random pattern blocks” examples will provide good test cases for tightening precision handling. If nothing else, this technology stack is likely to show up again at subsequent summer schools, where we might be able to look into open questions about the types of patterns produced by pattern blocks:
⟶ Enumerate the pattern block multiway graph to subsequent levels and count how many unique patterns are possible as a function of tile count.
⟶ Develop an algorithm for growing pattern block tilings without holes. Is it always possible to identify inert configurations immediately? Or do some inert configurations look okay until forced tiles have been added?
⟶ Given a pattern block pattern, estimate the difficulty of obtaining it by random evolution (probably under some additional constraints).
⟶ Explore if / when / how questions about pattern blocks can be solved by grid-based methods such as FindExactCover or SatisfiabilityInstances.
It must be stressed that failures of PlanarPolygonFragmentation shown here are a relatively benign issue, and not a sufficient reason to abandon its development. The argument is that it should go on to a second round of development as a consequence of its reliable behavior when iterated through many subsequent edge joins. Not only are the region system functions largely-incapable of handling infinite precision, under the same sort of iterative stress testing seen here, built-in functions such as RegionIntersection are known to reliably crash the kernel.
If you’re hoping to see more computer proofs about odd-shaped tilings (or partial tilings) in the future, please up-vote PlanarPolygonFragmentation. With enough interest now, the first quality revision can probably be completed before the next major version release, #15. But if there’s not enough interest, maybe it will have to wait for another generation of researchers to break out of the status-quo and end up doing something daringly imaginative with their free-time.
And stay tuned for more details about a new proof of the hat tiling, where we succeeded at neatly avoiding most of the precision errors seen here.
CITE THIS NOTEBOOK
CITE THIS NOTEBOOK
Don't forget the "Pattern Blocks”!
by Brad Klee
Wolfram Community, STAFF PICKS, November 7, 2023
https://community.wolfram.com/groups/-/m/t/3061504
by Brad Klee
Wolfram Community, STAFF PICKS, November 7, 2023
https://community.wolfram.com/groups/-/m/t/3061504