Contents
-
Imperfect Congruence
- A mathematical note
- About the author
- Part 1: Kepler and the regular polygon tilings
- Part 2: Rhomb/rhombus/rhombic tilings
-
Part 3: A universal tiler
- Fans and other rhombic structures
- Regular polygon decomposition
- Regular polygon decomposition (odd)
- Worms and zonagons
- Decomposition algorithm
- Decomposition mathematics
- Variations on the universal tiler
- The regular polygon extension theorem
- The triangle extension theorem
- The rule of two
- The vertex figure extension conjecture
- Vertex figure extension examples
- More vertex figure extension examples
- Part 4: Five-fold symmetry
- Conclusion
- Tiling Gallery
- Appendix: Bridges conference
- Appendix: Proof of the Gap Theorem
- Appendix: Tiling source code
Part 3: A universal tiler
Alice's Adventures in Wonderland
No.
In fact, amazingly, there is an algorithm to efficiently construct a translational unit for a periodic tiling of the plane from rhombs, triangles and any regular polygon!
The existence of an efficient universal tiling algorithm for regular polygons is surprising because many such general problems in tiling theory turn out to be undecidable or to require time-consuming NP-complete algorithms. For example, in 1966 David Berger showed that no algorithm could exist to automatically construct tilings from even simple prototile sets of Wang tiles.
However, the situation for rhombs and regular polygons is different. Sampath Kannan and Danny Soroker (1992) and Richard Kenyon (1993) independently developed an efficient algorithm to decompose certain finite simple polygons into rhombs (and more generally, parallelograms), and a modification of this algorithm can be used to construct periodic plane tilings also involving regular polygons as explained in the following sections.
Here’s an example involving hendecagons (11-sided regular polygons) constructed using a prototile set that also includes rhombs and triangles:
I’ve created a larger 1280x1024 image of this beautiful tiling.
You can download an SVG file for a translational unit for this tiling here.
In the next few sections I’ll describe the algorithm and provide the mathematical background for a universal regular polygon tiler.
