Grid-based Decorative Corners

Year: 2013 Authors: Craig S. Kaplan

Core claim

Square-grid corner motifs can be formalized, enumerated, and visually explored as a mathematically rich design space with meaningful aesthetic structure.

Topics

decorative corners, enumeration, routing words, aesthetic constraints

Domains

graph theory, combinatorics, planar graphs, symmetry, ornament, border design, geometric pattern, illustration software

Methods

grid-based formalization, enumeration, interactive software exploration, connectivity constraint

Media

square grid, digital design software, historical ornament examples, stock image references

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.

Proceedings of Bridges 2013: Mathematics, Music, Art, Architecture, Culture

Grid-based Decorative Corners

Craig S. Kaplan Cheriton School of Computer Science University of Waterloo csk@uwaterloo.ca

Abstract

I explore a space of geometric, decorative corner designs based on paths through a square grid. I discuss the problems of enumerating corners of a given size efficiently, and exploring them interactively in software. I then impose a higher-level connectivity constraint on corners and discuss the effect of this constraint on the mathematical and aesthetic properties of corner designs.

1 Introduction

Every canvas has a border, and in the decorative arts many traditions have evolved for applying an ornamental treatment to that border, be it in the medium of paper, fabric, or architecture. It is easy to find examples of decorative borders consisting of floral or other naturalistic patterns, but more abstract, geometric examples exist too. Some classic examples of purely geometric border designs from the Greek and Pompeian traditions are shown in Figure 1. We can also find geometric borders in Celtic art (particularly knotwork and key patterns [1]) and Islamic art (star patterns).

The most obvious canvas shape to be dealt with is a rectangle; but rectangles have corners, and border designs must be adapted carefully to fill those corners in a cohesive manner. Often, the solution lies in defining a special corner motif that is stylistically compatible with the (usually repeating) units that make up the edges. This approach is also common in contemporary illustration software; for example, Adobe Illustrator’s “Pattern Brush” supports up to five distinct modular tiles, including two for corners (for both convex and reflex vertices). In other cases, decorative corners are left to float free, and they reach towards each other, implying a frame around the entire canvas.

In this paper, I consider a highly abstract, restrictive decorative corner style, made up of rectilinear paths that lie on the edges of a square grid. The grid is expected to sit at or near the corner of a larger rectangle, with equal numbers of “wires” entering and leaving it parallel to the edges that meet at that corner. The wires interact by tracing out paths through the grid, and the overall design is symmetric across the diagonal (the bisector of the corner). The design is copied by reflection to the other three corners of the rectangle. The top of this page is flanked by a pair of such corners.

My most direct source of inspiration is a design I happened to see on the cover of a restaurant menu in Lisbon, Portugal; the design is reproduced in Figure 2. (The original design deviates slightly from a square grid, likely for aesthetic reasons.) It is not too difficult to find other examples of corner elements with a similar grid-based structure. Figure 3 shows three examples redrawn from a Shutterstock, a popular stock image repository.

My goal in this paper is to discuss some of the interesting mathematical and computational problems that arise in developing software to analyze and edit these grid-based decorative corners. I also hope that these corners might provide a fruitful microcosm in which to explore broader problems in the intersection of mathematics and aesthetics, and of course I wish to offer a space of designs that might be used productively in a practical setting.

Kaplan

Figure 1: Three historical examples of geometric border designs that include decorative corners, all taken from Jones’ Grammar of Ornament [2]. From left to right: Greek (Plate 15), Greek (Plate 22), Pompeian (Plate 25). The figures have been reoriented relative to Jones’ drawings.

Figure 2: A decorative corner redrawn from the menu of Os Tibetanos, a Tibetan restaurant in Lisbon, Portugal. The drawing on the left shows the design as it appeared on the menu; the bottom-right square is scaled down slightly, probably to lend the overall corner a more rounded appearance. The drawing on the right shows the design mapped to a strict square grid.

2 Foundations

I begin by giving a precise account of the space of mathematical objects in which we will be operating. Let $n$ and $k$ be positive integers; A single corner will consist of $k$ “wires” that enter along each of two edges of the corner, and interact with each other in an $n\times n$ grid of squares. I refer to the resulting diagram as an ” $(n,k)$ -corner design”.

I assume the grid is oriented on a page with a well defined top, bottom, left and right, and use those and related terms to describe relative and absolute positions in the grid. Let us arbitrarily choose to imagine the grid as being associated with the bottom-right corner of a rectangular page (the design can be mapped to any other corner via reflections). In this case, one set of $k$ wires will be stacked bottom-to-top along the left edge of the grid, and another set will be stacked right-to-left along the top edge. I arbitrarily designate the wires on the left edge the “input wires” and the wires on the top edge the “output wires”, even though they are perforce equivalent by the planned symmetry of the corner. These wires meet the grid at $2k$ grid vertices that I refer to as $k$ “input pins” and $k$ “output pins”. This configuration is depicted schematically in Figure 4.

The goal is to extend the wires into the grid so that they trace paths along edges. In the process, a subset of the edges of the grid will be considered “used” by the paths. The set of used edges (to which the input and output wires have been attached), together with the vertices incident to those edges, form a planar graph; it will occasionally be useful to use basic terminology from graph theory to discuss these designs. For example, we should allow paths to cross; a crossing corresponds to a vertex of degree 4 in the graph, in which alternating incident edges are paired to form long paths. On the other hand, we do not wish paths to end or form T-junctions in the middle of a corner: paths should either form closed loops, or start and end at the free ends of wires.

Grid-based decorative corners

Figure 3: Three examples of grid-based corners redrawn from Shutterstock, a popular stock image website. The design on the left is from an illustration titled “frame geometry” [3]; the two on the right are from “Decorative border from the bound lines in the Celtic style” [4].

Figure 4: On the left, a schematic showing the components of a corner design and the terminology used to describe it. On the right, an example based on the schematic, in this case a (5,2)-corner design.

Based on the concepts set forth above, we might immediately identify a few simple restrictions. First, we must have $k\le n+1$ — there cannot be more wires than there are vertices to hold pins. Second, every vertex in the grid must have degree 0, 2, or 4, except for the free ends of wires.

3 Enumeration

Given the definitions of the previous section, the question arises immediately of enumeration: how many $(n,k)$ -corners are there for different choices of $n$ and $k$ , and can we enumerate those corners efficiently?

An $n\times n$ grid has $2n(n+1)$ edges. But these corner designs are intended to be symmetric across the diagonal, meaning that exactly half of the edges (say, the half above the diagonal) are determined from the other half, leaving $n(n+1)$ non-redundant edges. Naively, we could try all $2^{n(n+1)}$ possibilities for which edges to use in the graph, and eliminate those combinations that contain vertices of degree 1 or 3. However, this approach is unnecessarily inefficient. In the example of Figure 2, $n$ is at least 8, meaning that it belongs to a set of graphs of size at least $2^{72}\approx 4.7\times 10^{21}$ . And many of these graphs will be eliminated for trivial reasons, since for each vertex, only eight of the 16 possible configurations of used edges around that vertex (i.e., those with degree 0, 2, or 4) can possibly appear in a legal design.

A better starting point is to consider edges in coupled pairs. Let us focus on one vertex in the grid, and assume

Kaplan

Figure 5: For each possible pair of edges entering a vertex from below and to the left, there are exactly two possible pairs of edges leaving up and to the right. By adhering to these combinations, we can avoid producing graphs with vertices of odd degree.

Figure 6: A sequence of single-cell transformations that transform an initial trivial corner (top row, left) into the corner design of Figure 2. Each frame has a shaded grid cell; this cell’s edges are inverted to produce the next frame. The edges surrounding the symmetric copy of the cell are always transformed at the same time.

that we have previously decided upon the states (used versus unused) of the edges entering from below and to the left. There are four possible combinations of those two incoming edges, all of which may occur in real designs. However, for each of these incoming configurations, it is easy to see that there are only two possible configurations for the edges leaving up and to the right, as shown in Figure 5. Note also that the incoming configuration of the bottom-left corner of the grid is fixed (one edge coming from the left, no edge from below). Combining these facts, we can construct all possible designs by beginning at the bottom left and working upward in rows, making a binary choice at every vertex until we reach the main diagonal. The edges above the main diagonal are constructed by reflection. There are exactly $n(n+1)/2$ vertices below the diagonal, and therefore $2^{n(n+1)/2}$ designs to consider, the square root of the number in the naive approach. For $n=8$ we must consider $2^{36}\approx 68$ billion possibilities, a large number but within the range of an average computer. Moving to $n=9$ takes us into the tens of trillions.

This argument shows that the number of $(n,k)$ -corners can be determined from a simple expression that does not depend on $k$ . We will encounter a more complex enumeration question in the presence of additional graph-theoretic constraints, as introduced in Section 5.

4 Interactive editing

In order to make these corners practical for use in illustration, it should be possible to manipulate them intuitively in an interactive user interface. Enumeration might be interesting mathematically, but interactive exploration will be more useful to a designer than a static list of every possible corner design of a given size.

Grid-based decorative corners

As in the naïve approach above, an interactive tool might simply allow the user to enable or disable each edge of the grid interactively; it would then be up to them to ensure that there are no vertices of odd degree. However, it is preferable to offer the user a tool that manipulates the edges without disrupting the connectivity constraints of Section 2, turning legal graphs into other legal graphs.

It turns out that a simple operation can serve as a minimal unit of editing for these corners: the user selects (e.g., clicks on) a cell of the grid, and we invert the states of the four edges surrounding that cell. This operation is guaranteed to preserve the parity of all edges in the graph (a fact that can be seen by considering all possible cases), and every legal graph can be constructed via a suitable sequence of these operations. Figure 6 shows one sequence of steps for producing the design of Figure 2. This process also provides an alternative justification of the enumeration in the previous section, because the set of legal graphs can be derived from the parities of the $n(n+1)/2$ grid squares below the diagonal.

I have created a simple Java interface that permits this sort of interactive exploration. The interface begins in a trivial state in which each input wire is routed directly across and up to its corresponding output wire. The user can save their final design in a Postscript file for use in a practical decorative context (and for further manipulation in a drawing tool such as Adobe Illustrator). When creating its output, the program joins individual edges into rectlinear paths of maximal length (including closed loops), which facilitates applying colouring or other decorative treatments later.

5 Aesthetic constraints

At this point we have an enumeration of $(n,k)$-corner designs that depends only on $n$. For example, there are 1024 $(4,2)$-corners. But not all of these designs are created equal. Fortunately, with the ability to explore large spaces of possible designs, it becomes possible to articulate further constraints that narrow our focus to a subset of designs that we deem to be aesthetically pleasing.

The most natural constraints relate to the connectivity between the wires, and the paths that are traced out between input and output pins. After some experimentation, I offer these three constraints:

• The two halves of the pattern should connect across the diagonal; that is, there should be at least one path in the graph from an input pin to an output pin. (“Path” is used here in the graph-theoretic sense, and includes the possibility of following a left or right neighbour at a degree 4 vertex.);
• The design should not contain any closed loops that are disconnected from the main body of the design; and
• The wires connecting input and output pins should not decompose into disconnected sets. (For if they do, we can just as well regard the result as the juxtaposition of independent designs.)

All of these constraints can be satisfied by imposing a single, global topological restriction on the design: the associated graph must consist of a single connected component. I refer to the resulting subset of designs as the “fully connected” corners. I am not aware of an efficient enumeration technique tailored to fully connected corners. Instead, I rely on enumerating all legal corners as in the previous section, and perform a depth-first search of the resulting graphs to filter out those that have multiple disconnected components.

The fully connected corners seem to strike an appropriate balance between mathematics and aesthetics. A complete set of fully connected $(n,k)$-corners for $n\le 3$ is shown in Figure 7. The figure highlights the fact that if m<n, then every $(m,k)$-corner can be seen as a degenerate case of an $(n,k)$-corner (in which the wires are drawn $n-m$ units longer than necessary). The figure begins a longer enumeration of the number of fully connected corners of various sizes. Based on the output of an offline program, the enumeration continues as in the table

Kaplan

Figure 7: The complete set of fully connected $(n,k)$ -corners for $n\le 3$ . The figure is laid out to highlight the division into $(3,k)$ corners for all possible values of $k$ , but each section also highlights those designs that can also be considered $(1,k)$ -corners or $(2,k)$ -corners.

below. One might hope to discover that the columns are well known integer sequences; however, they do not seem to arise in the Online Encyclopedia of Integer Sequences [5].

It is interesting to note that unlike the general case, the number of fully connected corners now depends on $k$ . As $k$ increases, more wires are fighting for the same number of grid edges, which restricts each wire’s freedom of

Grid-based decorative corners

Figure 8: On the left, a grid for constructing a (3,3)-corner with input and output pins labeled as in Section 6. On the right, a partition of the fully connected (3,3)-corners for which the input wires are connected to the output wires via a permutation.

movement and hence the number of possible designs.

6 Routing

Regardless of whether we are examining general corner designs or only those that are fully connected, any wire that enters at some input pin will eventually leave by one of the input or output pins. We might then use the manner of these interconnections as a high-level summary of the behaviour of the corner, or as a means of partitioning them into different classes. With that in mind, I label the $k$ input pins from bottom to top as $i_1,\dots ,i_k$, and the $k$ output pins from right to left as $o_1,\dots ,o_k$, as shown in Figure 8. It is then possible to describe the interconnection via a “routing word”, a $k$-character word on the alphabet of pin names, simply by listing the destinations of the paths that begin at the $k$ input pins. This word fully specifies the destination of every wire connected to the design. If $i_a$ connects to $i_b$, then by symmetry we must also have $o_a$ connecting to $o_b$; similarly, if $i_a$ connects to $o_b$, then $i_b$ must also connect to $o_a$.

Based on this notation, it then becomes possible to analyze corners in terms of their routing words. Consider, for example, the (3,3)-corners, and let us focus on those interconnections for which every input pin is connected to an output pin. Because of the symmetry noted in the previous paragraph, there are four legal routing words in this context: $o_1{o}_2{o}_3$, $o_3{o}_2{o}_1$, $o_1{o}_3{o}_2$, and $o_2{o}_1{o}_3$ (that is, we eliminate the two permutations of the output pins that leave no pin fixed). The fully connected (3,3) corners with these routing words are shown in Figure 8. Note that no corners of this size exist with routing word $o_2{o}_1{o}_3$; the two inner wires simply cannot maneuver around each other while leaving the outer wire unaffected. Another interesting observation concerns the $(n,2)$-corners. There are only three possible routing words when $k=2$: $i_2{i}_1$, $o_1{o}_2$ and $o_2{o}_1$. But $o_2{o}_1$ cannot occur unless $n\ge 3$, again because smaller grids do not offer enough wiggle room to achieve some interconnections.

After examining many of these designs, it seems as if we might want to impose a further aesthetically motivated restriction based on routing words, namely that the word is a permutation of the output pins (so that every input wire travels through the grid and leaves by an output wire). For the most part, I find it undesirable to have an input wire $i_a$ curve back to leave again at $i_b$. This rule does not feel as universal as full connectivity, but it is worth considering further.

7 Discussion

Most of this paper has been concerned with the mathematical structure of corner designs, but of course they also serve an aesthetic goal, as a space in which to discover interesting new corners for use in illustration. Figure 9 shows four examples of a (6,3)-corner design decorated in different styles. Independent strands can be high-

Kaplan

Figure 9: An example of a (6,3)-corner design, rendered in four distinct visual styles.

Figure 10: Two $(n,k)$ -corners can be superimposed to create a single $(2n+1,2k)$ -corner. Either of two original corners can be shifted up and to the left, resulting in two distinct designs.

lighted by giving them different colours, as in the third example from the left. Two other examples demonstrate the fact that all corner designs can be drawn consistently in an interlaced style, another consequence of the fact that every grid vertex has even degree. Multiple independent designs can also be combined cleanly, as shown in Figure 10. For example, any two $(n,k)$ -corners can be superimposed, offset by half of the side length of a grid square, to produce a new $(2n+1,2k)$ -corner.

For future work, it would be worthwhile to explore the extent to which this microcosm might reveal meaningful insights into the human aesthetic response to ornament. Such insights would likely emerge from perceptual studies. For example, of the 21 fully connected (3,2)-corners, are some rated consistently as more or less attractive than others? If so, why? Are there geometric features of these designs that can be associated with their perceived aesthetic quality? We might then hope that any results in this area could be used as a starting point for studying the perception of patterns and ornament.

References

[1] Iain Bain. Celtic Key Patterns. Sterling Pub Co Inc., 1994. [2] Owen Jones. The Grammar of Ornament. Studio Editions, 1986. Available online at http://digital.library.wisc.edu/1711.dl/DLDecArts.GramOrnJones. [3] Shutterstock. Decorative border from the bound lines in the celtic style. http://www.shutterstock.com/pic.m?id=31562680. Accessed 22 April 2013. [4] Shutterstock. Frame geometry. http://www.shutterstock.com/pic.m?id=54305494. Accessed 22 April 2013. [5] N. J. A. Sloane. The On-Line Encyclopedia of Integer Sequences. http://oeis.org/. Accessed 22 April 2013.