Constellations of Form: New Compositional Elements Related to Polyominoes
Year: 2006 Authors: James Mai; Daylene Zielinski
Core claim
Strutforms generalize polyomino dual graphs into richer complete families that support new tiling interpretations and visual compositions.
Topics
polyomino dual graphs, permutation-based form families, digital print composition, tiling interpretation
Domains
graph theory, combinatorics, lattice animals, enumeration, generative art, digital printmaking, visual composition, painting
Methods
permutational enumeration, dual graph construction, cycle reduction, close-packed arrangement
Media
point arrays, strutforms, digital prints, paintings
Paper text
The text below is the locally extracted OCR/Markdown version of the paper. Raw PDF files remain local and are not published here.
James Mai
School of Art
Campus Box 5620
Illinois State University
Normal, IL 61790-5620, USA
E-mail: jlmai@ilstu.edu
Daylene Zielinski
Mathematics Department
Bellarmine University
2001 Newburg Road
Louisville, KY 40205, USA
E-mail: dzielinski@bellarmine.edu
Abstract:
A predominant theme of artist James Mai’s compositions is the development of finite sets of related objects derived from permutational processes. Each element is distinct, yet all of them share particular features. Thus, he develops families of objects that are at once diverse since each object is visually distinct and integral since the set of objects is exhaustive. These objects provide the elements for combination and composition in paintings and digital prints. Recent permutational investigations by Mai have yielded objects we call point arrays and strutforms, which are related to polyominoes via dual graphs. These new objects, however, have greater variety than polyominoes and offer some new opportunities for a different interpretation of tilings. The results of these investigations are visible in the digital print, Heart of Sky, which includes the complete sets of 3- and 4-strutforms in a “close-packed” or minimal area arrangement. Mai is currently working on compositions with the set of 5-strutforms.
1. The Evolution of Strutforms
A consistent theme in the work of artist James Mai is the drive to produce complete sets of visually distinct forms that share a particular visual and/or mathematical quality defined by the artist. The objects we are about to introduce were developed by just such an organic artistic and mathematical investigation. Mai’s initial investigation into these objects began as permutations of arrays of points in a square grid prompted by the following question: How many visually distinct ways can four points be arrayed at adjacent intersections of a square grid? Requiring that each form be visually distinct omits duplication of forms that are merely rotated or reflected versions of others in the same family. Thus, each of the remaining forms is unique. With four points, the family of unique forms is small; there are only five such arrays, which are shown in Figure 1a.
Figure 1a: 4-point arrays.
Figure 1b: The five tetrominoes.
Mathematically, a slight change in perspective reveals a deep connection to polyominoes, which are collections of unit squares joined along edges to form a polygon [1]. If we place the points at the centers of adjacent squares in the grid rather than at intersections of lines in the grid, we can now see the tetromino underlying each 4-point array as shown in Figure 1b. In fact, this figure makes it obvious that Mai’s 4-point arrays and the set of tetrominoes can be put into one-to-one correspondence. So, it should come as no surprise that there are exactly five 4-point arrays, since there are exactly five tetrominoes. For this same reason, there are exactly twelve 5-point arrays, which are displayed in Figure 2a. Positioning points in the center of each square in a polyomino is the first step to forming its dual graph, so Mai’s investigation of point arrays coincided with enumerating the vertex structures of the dual graphs of polyominoes.
As Mai continued his exploration of these point arrays, he added edges between pairs of points that were connected along grid lines. This set of forms is displayed in Figure 2b. Although he originally did this as a visual aid so that he could quickly determine which point arrays were visually distinct, Mai quickly discovered that shifting his focus from points to the connecting edges produced a richer set of forms because the last form in Figure 2b is different from the others. It alone has five edges, although each of the other forms has only four edges. As Mai sought to bring this unique 5-edge form into accord with the rest of the 4-edge forms his investigation had yielded, he revised his original motivating question in the following manner: How many ways can four edges along grid lines be arranged so that they connect adjacent intersections points? A complete set of these forms is shown in Figure 3 below. We will refer to these objects as 4-strutforms, and it is at this juncture in Mai’s investigation that his forms evolve beyond their polyomino ancestors.
Figure 2a: The twelve 5-point arrays.
Figure 2b: The dual graphs of the pentominoes.
At the point when Mai first introduced the edges to his point arrays, he had created the dual graphs of the polyominoes, since adding grid line edges to Mai’s point arrays is tantamount to adding edges between points centered in adjacent squares in the underlying polyomino. However, Mai’s decision to limit the number of edges to four forces the unique form with five edges in Figure 2b to fracture into four visually distinct 4-strutforms, which are shown in the first row of Figure 3. Furthermore, one of the tetrominoes has a dual graph with four edges, and thus this graph is also a 4-strutform and appears as the
last form in Figure 3. Hence while there are only twelve pentominoes, there are sixteen 4-strutforms, only eleven of which are dual graphs to a pentomino.
Figure 3: Mai’s sixteen 4-strutforms.
2. Strutforms as Mathematical Objects
The preceding discussion of the development of -strutforms makes it clear that they are closely related to the dual graphs of -ominoes, but this relationship must be placed on firm mathematical ground. To preserve as much of the artist’s original vision as possible, we will begin with a definition that is not as mathematically economical as it could be. We shall define an -strutform as a connected graph with exactly edges, whose vertices are centered in squares that form a grid; furthermore, edges can only occur between pairs of vertices that are centered in adjacent squares. Thus, our formal mathematical definition shall be as follows: an -strutform is any connected subgraph with exactly edges of the graph created by an square grid.
The process for creating the set of -strutforms is relatively straightforward. One begins with the dual graphs of the -ominoes, which are formed by replacing each unit square with its center-point and adding edges between each pair of points that are centered in adjacent squares of the original polyomino. Next, we need to check each of these dual graphs for cycles, which are paths of edges in a graph that begin and end at the same vertex. If the dual graph of an -omino has no cycles, then it will have exactly edges and automatically be an -strutform. If, however, the dual graph does have cycles, then it will have more than edges, and at least one edge will need to be removed to create a -strutform. Since strutforms must be connected, it is not valid to remove an edge or edges that cause the dual graph to become disconnected. The number of edges that must be removed depends on the cycle index of the graph, which is the minimal number of edges that must be removed from the graph so that it no longer has any cycles. For example, if we remove any one edge of the graph shown in Figure 4a, there will be at least one cycle still remaining; however, if we remove two of the vertical edges, the remaining subgraph will have no cycles, yet still be connected. Thus, the cycle index of the graph in Figure 4a is two. Luckily, the cycle index of a graph is simple to compute; the cycle index of any graph is the number of edges minus the number of vertices plus one. Note that the graph in Figure 4a has seven edges and six vertices, so its cycle index is two, not three, even though there are three distinct cycles in this graph. So, one must remove two edges from this graph to create 5-strutforms or one edge to create 6-
strutforms. This one graph, which is a 7-strutform on its own, generates six distinct 5-strutforms and three distinct 6-strutforms.
The mere presence of a cycle in an -omino’s dual graph does not insure that it will fracture into multiple -strutforms because the symmetry of the graph also plays a role. For instance, the graph in Figure 4b, which is the dual graph of the square tetromino, has a cycle, but removing any one edge produces the same 3-strutform because the reflective symmetries alone of the original graph, which are shown as dashed lines, make each of its edges equivalent. An asymmetric dual graph of any -omino with exactly one cycle, will fracture into as many -strutforms as there are edges in the cycle. This is why the last graph in Figure 2b generates four distinct 4-strutforms. The graph in Figure 4c, with its one symmetry that makes two pairs of the edges in its single cycle equivalent, will produce only two distinct 5-strutforms. In fact, the question of how many distinct -strutforms will be generated by any particular polyomino’s dual graph is a question best answered by Burnside’s Theorem. The process of applying this result to questions of this type is demonstrated in [2].
When removing edges from a graph, it is important to remember that the vertices remain. Because -strutforms must be connected, we cannot remove all edges incident to any one vertex, thereby creating an isolated vertex. Hence, the 4-strutform in Figure 4b above cannot be generated from the last graph in Figure 2b; removing the single edge that is not part of the cycle would create an isolated vertex and, thus, a disconnected subgraph. So, we cannot rely on the dual graphs of the -ominoes alone to create the full set of -strutforms. In fact, whenever the dual graph of any -omino where k - 1 < n has cycle index equal to , then that dual graph will be an -strutform. This is exactly why the graph in Figure 4a, which is dual to a hexomino and has a cycle index of two, is a 7-strutform .
3. Visual Encoding and Composing
Once any system of forms is complete, Mai develops a compositional organization that seeks to be as clear, complete, and efficient as possible in reference to the system. In the development of Heart of Sky, Figure 5, clarity was sought by encoding in color, scale, and distribution the many shared and distinct characteristics of the strutforms, including not only the different organizations of points and struts, but also the acknowledgment of symmetrical and asymmetrical forms. For Mai, compositional completeness demands the inclusion of every distinct form in the system, without the repetition of any form by symmetric translation, rotation, or reflection. Efficiency was sought by “close-packing” the set of strutforms in the minimum area.
When considering the close-packing possibilities, Mai examined the characteristics of both the individual strutforms and their families for appropriate possibilities. The sixteen unique 4-strutforms required 79 points in the lattice since fifteen of these strutforms require five points each and one requires only four points. This offered the possibility of a composition in a square point lattice leaving two points unused. On further consideration, Mai opted to combine the 4-strutforms with the 3-strutforms bringing the total number of points needed for the strutforms to 99, which leaves one unused point in a 10
x 10 square point lattice. Mai visually encoded two additional types of information about the strutforms in the final work. First, he acknowledge the difference between the 3-strutform and the 4-strutform families by orientation within the grid. Hence, each group is set at a different angle within the point lattice and each group is a different pair of complementary colors—red and green for the 3-strutforms and blue and orange 4-strutforms. Secondly, Mai wanted to distinguish between asymmetrical strutforms and those having either rotational or reflective symmetries. This also was accomplished through color by reserving the two primary colors, red and blue, for those strutforms with at least one symmetry.
Figure 5: Heart of Sky, digital print, inches.
356
4. Strutforms, Tilings, and an Open Question
Since strutforms are a richer set of objects than the related polyominoes, it makes sense to investigate what advantage strutforms may have over the traditional polyominoes. In particular, the topic of primary interest where polyominoes are concerned is tilings. Since strutforms do not have any area, traditional tilings do not make sense; however, we can take a cue from Mai’s artwork, Heart of Sky, and investigate a different interpretation of tilings. What we see in Heart of Sky is the 3- and 4-strutforms arranged on a point lattice. Indeed, if we recall the origin of the strutforms, it seems quite appropriate to position them on the vertex structure of the dual to the square grid. Therefore, we will call any arrangement of strutforms that covers each point in a lattice with the vertices of the strutforms without any overlapping a point lattice covering.
It is a well-known result that if any block is removed from the standard checkerboard, the remainder of the board can be tiled with the twelve pentominoes; for a proof of this see [1]. To translate this into the setting of point lattice covings using strutforms, we will replace the unit squares of the checkerboard with a point at the center of each square and remove the grid lines completely so that we are left with an point lattice. In this manner, any tiling with pentominoes has a dual point lattice covering with 4-strutforms. Since the set of 4-strutforms includes the dual graph of the square tetromino, shown in Figure 4b, this special strutform can be used to cover the section of the dual point lattice that corresponds to the hole left by the pentomino tiling of the standard checkerboard. Thus, we arrive at the following result.
Regardless of where the 4-strutform that is dual to tetromino is placed in an point lattice, the rest of the lattice can be covered with other 4-strutforms.
Further inspection of Mai’s Heart of Sky suggests yet another possibility for using strutforms to cover point lattices. Notice that Mai has rotated his point lattice through a 45-degree angle. Beyond this, he has visually distinguished between the 3- and 4-strutforms in Heart of Sky by using a different orientation for the two sets. This is tantamount to the artist allowing the unit measurement of the composition to vary. The unit length for the family of 4-strutforms is the distance between the adjacent grid squares arranged at a 45-degree angle; however, the 3-strut forms are oriented differently so that the length of one strut is now equal to the diagonal of one grid square rather than just the length of one side of a grid square. This longer unit strut length allows the 3-strutforms to interact in a distinctly different manner: the 3-strutforms in Heart of Sky can interlock with each other as seen in center just below the isolated point. Therefore, strutforms can interact in a point lattice covering in a manner that their dual polyominoes cannot in any grid tiling.
We can take advantage of this interlocking behavior without changing the unit strut length by using a double point lattice, created from the standard square grid and its dual by using both the points at grid line intersections and the points at the center of each grid square. In the standard checkerboard, this would create a double grid of 145 points—64 points from the dual grid and 81 points from grid line intersections including those on the outer edges of the board. This suggests an open question.
Can the double point lattice of the standard checkerboard be covered with the 4-strutforms having unit strut length equal to the side of one square in the checkerboard?
There are clearly some restrictions as to how the 4-strutforms can be used in such an endeavor. Most obvious is that the 4-strutform that played such a vital role in our first result above is now anathema. If the 4-strutform that comes from the dual graph of a tetromino is placed anywhere in this doubled grid, it will isolate a point, as shown in Figure 6, making a covering impossible. There are similar kinds of restrictions, such as how far many of the other 4-strutforms must be from the edge of the doubled point
lattice to avoid creating other isolated points, but the answer to the question posed above has eluded the authors thus far.
Figure 6: Tetromino-based 4-strutform isolating a point in a double point lattice.
5. Figurative Allusions
Mai’s shift in focus from point arrays to strutforms did more than push his objects from a mathematically known set into the unknown, it also presented the artist with an overarching metaphor for the final composition. From the beginning, recognition of the distinct point arrays required the visual grouping of disparate parts into understandable wholes, a perceptual process that Mai found akin to recognizing constellations in the night sky. Adding struts to his original point arrays, and thereby creating connected graphs, strengthened this identification with constellations and, from an early stage, helped guide the subject matter and metaphoric references that would eventually emerge in the finished composition.
With this astronomical reference in mind, the sole, unused point in the lattice seemed equivalent to Polaris, the star around which the night sky revolves. This helped to guide the compositional decisions as Mai worked intensively to find an arrangement that would not only close-pack the strutforms but also locate that single, isolated point near the top and on the vertical axis of the lattice, as suggestive of the North Star. Only one solution was found that fulfills all of the above conditions, realized in the final large-scale digital print. The title, Heart of Sky, derives from the name given by ancient Maya astronomers to the north celestial axis about which the night sky appears to turn [3].
6. Further Investigations
This line of investigation continues with the development of the 5-strutform family. Mai’s 35 unique 6-point arrays are coincident with the vertex structure of the dual graphs of the 35 hexominoes. Among these, there are 27 hexominoes whose dual graphs have no cycles; these translate directly to 5-strutforms, which are seen in Figure 7a. Eight of the hexominoes, however, have dual graphs that contain cycles, each of which creates several distinct 5-strutforms. These strutforms are shown in Figure 7b grouped in families that are all subgraphs of the same dual hexomino. Also shown at the bottom right of Figure 7b is the one 5-strutform that is dual to a pentomino. Since 54 of these require six vertices and the remaining one uses five vertices, any composition of these 5-strutforms will require 329 vertices in a point lattice. The system is complete; final compositional solutions are still in progress.
Mathematically, the task of enumerating -strutforms for a given is non-trivial; note that the process of computing the number of -strutforms for a particular is at least as difficult as the related, and still unsolved, problem of enumerating -ominoes. Further note, that enumeration results for spanning trees will be helpful for small values of , but for larger , many of the -strutforms will not be trees. There has been much work done on enumeration of lattice animals, of which polyominoes are a subset, because this problem relates to questions about percolation in physics. Readers interested in this line of investigation would do well to start with the works of A. R. Conway, M. Delest, and E. Jensen.
Figure 7a: Mai’s 5-strutforms that correspond directly to dual graphs of hexominoes.
Figure 7b: Mai’s 5-strutforms that are subgraphs of dual graphs of hexominoes and the single 5-strutform that is dual to a pentomino.
References
[1] S. W. Golomb. Polyominoes: Puzzles, Patterns, Problems, and Packings. Revised Edition. Princeton University Press, 1994. [2] J. Mai and D. Zielinski. Permuting Heaven and Earth: Painted Expressions of Burnside’s Theorem. In Conference Proceedings of Bridges: Mathematical Connections in Art, Music and Science, 2004. Eds. Sarhangi, Reza and Séquin, Carlo. [3] Friedel, D., L. Schele, and J. Parker. Maya Cosmos: Three Thousand Years On the Shaman’s Path. New York: William Morrow & Co., 1993. [4] Palmer, S. E. Vision Science: Photons to Phenomenology. Cambridge: The MIT Press, 1999.