Tessellation designs composed from tiles in periodic space fillings are considered. An efficient algorithmic theory for the generation and enumeration of nonequivalent designs is developed. It is shown that each design has a graphical representation as a labelled subgraph of some graph whose vertices have associated integral coordinates. Detecting isomorphisms between designs then reduces to determining permutations of the labels of the vertices of this graph and may be performed in linear time. A proof of correctness for the algorithmic theory is provided. Nine specific algorithms for various families of designs from the archimedean tessellations are presented.
Get full access to this article
View all access options for this article.
References
1.
AhoA VHopcroftJ EUllmanJ D, 1974The Design and Analysis of Computer Algorithms (Addison-Wesley, Reading, Mass)
2.
BitnerJ RReingoldE M, 1975“Backtrack programming techniques”Communications of the ACM18651–656
3.
BolkerE DCrapoH, 1977“How to brace a one-story building”Environment and Planning B4125–152
4.
BondyJ AMurtyU S R, 1976Graph Theory and Its Application (Macmillan, London)
5.
CorneilD GMathonR A, 1978“Algorithmic techniques for the generation and analysis of strongly regular graphs and other combinatorial configurations”Annals of Discrete Mathematics21–32
6.
EdenM, 1958“A probabilistic model for morphogenesis” in Symposium on Information Theory in Biology Eds YockeyH P and others (Pergamon Press, New York) pp 359–370
7.
EdenM, 1960“A two-dimensional growth process”Proceedings of the Berkeley Symposium on Mathematical Statistics and Probability4223–239
8.
EdmondsJ, 1965“Paths, trees, and flowers”Canadian Journal of Mathematics17449–467
9.
FillmoreJ PWilliamsonS G, 1974“On backtracking: A combinatorial description of the algorithm”SIAM Journal on Computing341–55
10.
GauntD SGuttmanA J, 1974“Asymptotic analysis of coefficients” in Phase Transitions and Critical Phenomena, Volume 3 Eds DombCGreenM S (Academic Press, London) pp 181–243
11.
GolombS W, 1954“Checkerboard and polyominoes”American Mathematical Monthly61672–682
12.
GolombS W, 1961a“The general theory of polyominoes, part 1, dominoes, pentominoes and checkerboards”Recreational Mathematics Magazine43–12
13.
GolombS W, 1961b“The general theory of polyominoes, part 2, patterns and polyominoes”Recreational Mathematics Magazine53–12
14.
GolombS W, 1961c“The general theory of polyominoes, part 3, pentomino exclusion by monominoes”Recreational Mathematics Magazine63–20
15.
GolombS W, 1962“The general theory of polyominoes, part 4, extensions of polyominoes”Recreational Mathematics Magazine87–16
16.
GolombS W, 1965Polyominoes (Scribner, New York)
17.
GolombS WBaumertL D, 1965“Backtrack programming”Journal of the ACM12516–524
18.
HararyF, 1969Graph Theory (Addison-Wesley, Reading, Mass)
19.
HararyFMarchLRobinsonR W, 1978“On enumerating certain design problems in terms of bicoloured graphs with no isolates”Environment and Planning B531–43
20.
HararyFPalmerE M, 1973Graphical Enumeration (Academic Press, New York)
21.
HararyFPalmerE MReadR C, 1975“The cell growth problem for arbitrary polygons”Discrete Mathematics11371–389
22.
HararyFReadR C, 1970“The enumeration of tree-like polyhexes”Proceedings of the Edinburgh Mathematical Society171–13
23.
HorowitzESahniS, 1976Fundamentals of Data Structures (Computer Science Press, Woodland Hills, Calif.)
24.
KellyJ B, 1966“Polynomials and polyominoes”American Mathematical Monthly73464–471
KlarnerD, 1967“Cell growth problems”Canadian Journal of Mathematics19851–863
27.
KlarnerD, 1969“Methods for the general cell growth problem” in Combinatorial Theory and Its Application III Eds ErdosPRenyiASósV T (North-Holland, Amsterdam)
28.
KlarnerDRivestR L, 1973“A procedure to improve the upper bound for the number of n-ominoes”Canadian Journal of Mathematics25585–602
29.
LehmerD H, 1964“The machine tools of combinatorics” in Applied Combinatorial Mathematics Ed. BeckenbachF E (John Wiley, New York)
30.
LittlewoodD E, 1931“The groups of the regular solids in n-dimensions”Proceedings of the London Mathematical Society3210–20
31.
LunnonW F, 1969“Three combinatorial problems” PhD Thesis, Department of Mathematics, University of Manchester, Manchester
32.
LunnonW F, 1971“Counting polyominoes” in Computers and Number Theory Eds AtkinA O LBirchB J (Academic Press, London) pp 347–372
33.
LunnonW F, 1972“Counting hexagonal and triangular polyominoes” in Graph Theory and Computing Ed. ReadR C (Academic Press, New York) pp 87–100
MarchLEarlC F, 1977“On counting architectural plans”Environment and Planning B457–80
36.
MartinJ L, 1974“Computer technique for evaluating lattice constants” in Phase Transitions and Critical Phenomena, Volume 3 Eds DombCGreenM S (Academic Press, New York) pp 97–112
37.
MartinJ LWattsM C, 1971“The endpoint distribution of self-avoiding walks in a crystal lattice”Journal of Physics A4456–463
38.
PalmerE M, 1972“Variations of the cell growth problem” in Lecture Notes in Mathematics 303. Graph Theory and Its Application Eds AlaviYLickD RWhiteA T (Springer, Berlin) pp 215–224
39.
ParkinT RLanderI JParkinD R, 1967“Polyomino enumeration results” paper presented at the Society for Industrial and Applied Mathematics (SIAM) Fall Meeting, Santa Barbara, Calif.
40.
ReadR C, 1962“Contributions to the cell growth problem”Canadian Journal of Mathematics151–20
41.
ReadR C, 1978“‘Every one a winner’ or ‘How to avoid isomorphism search when cataloguing combinatorial configurations’”Annals of Discrete Mathematics2107–120
42.
ReingoldE MNeivergeltJDeoN, 1977Combinatorial Algorithms: Theory and Practice (Prentice-Hall, Englewood Cliffs, NJ)
43.
StinyGMitchellW J, 1978“Counting Palladian plans”Environment and Planning B5189–198
44.
SykesM FGauntD SRobertsP DWylesJ A, 1972a“High temperature series for the susceptibility of the Ising model I. Two-dimensional lattices”Journal of Physics A5624–639
45.
SykesM FGauntD SRobertsP DWylesJ A, 1972b“High temperature series for the susceptibility of the Ising model II. Three-dimensional lattices”Journal of Physics A5640–652
46.
SykesM FGlenM, 1976“Percolation process in two dimensions I”Journal of Physics A987–95
47.
SykesM FGuttmanA JWattsM GRobertsP D, 1972c“The asymptotic behaviour of self-avoiding walks and returns on a lattice”Journal of Physics A5653–660
48.
TarjanR E, 1972“Depth first search and linear graph algorithms”SIAM Journal on Computing1146–160
49.
TarjanR E, 1975“Efficiency of a good but not linear set union algorithm”Journal of the ACM22215–225
50.
TarryG, 1895“Le problème des labyrinthes”Nouvelles Annales de Mathématiques14187–190
51.
TilleyR C, 1970“The cell growth problem for filaments” in Proceedings of the Louisiana Conference on Combinatorics, Graph Theory and Computing (Louisiana State University, Baton Rouge, La); also MA Thesis, York University, Toronto
52.
WalkerR J, 1960“An enumerative technique for a class of combinatorial problems” in Combinatorial Analysis: Proceedings of Symposia in Applied Mathematics X Eds BellmanRHallMJr (American Mathematical Society, Providence, RI) pp 91–94
53.
WellsA F, 1977Three Dimensional Nets and Polyhedra (John Wiley, New York)
54.
WilliamsonS G, 1973“Isomorph rejection and a theorem of de Bruijn”SIAM Journal on Computing244–59
