|
|
The points of the Poincaré disk model are interior points
of a bounding circle in the Euclidean plane.
Hyperbolic lines are represented by diameters and circular arcs
that are orthogonal to the bounding circle [Greenberg].
The Poincaré disk model is attractive to artists because
it is conformal (angles have their Euclidean measure) and it
is displayed in a bounded region of the Euclidean plane, so that
it can be viewed in its entirety.
Escher was able to reconstruct the circular arcs in Coxeter's
figure and then use them to create his first circle limit pattern,
Circle Limit I, which he included with his letter to Coxeter.
Figure 2 shows a rough computer rendition of the
Circle Limit I design.
Coxeter's reprint shows
Escher's markings on the reprint that Coxeter sent to him shows
that the artist had found the centers of some
of the circular arcs and drew lines through collinear centers
[Schattschneider1].
|
|
The center of an orthogonal circular arc is external to the disk and is called its pole. The locus of all poles of arcs through a point in the disk is a line called the polar of that point [Goodman-Strauss]. The external dots in Figure 1 are the poles of the larger arcs, and the external line segments connecting them are parts of polars of the points of intersection of those arcs. The external web of poles and polar segments is sometimes called the scaffolding for the tessellation. The fact that the polars are lines can be used to speed up the straightedge and compass construction of triangle tessellations. For example, given two points in the disk, the center of the orthogonal arc through them is the intersection of their polars.
Coxeter explained the basics of these techniques in his return letter to Escher [Roosevelt], although by that time Escher had figured out most of this, as evidenced by Circle Limit I. Like Escher, mathematicians have traditionally drawn triangle tessellations in the Poincaré disk model using straightedge and compass techniques, occasionally showing the scaffolding. This technique was something of a geometric "folk art" until the recent paper by Chaim Goodman-Strauss [Goodman-Strauss], in which the construction methods were finally written down.
For positive integers p and q, with 1/p + 1/q < 1/2, there exist tessellations of the hyperbolic plane by right triangles with acute angles pi/p and pi/q. A regular p-sided polygon, or p-gon, can be formed from the 2p triangles about each p-fold rotation point in the tessellation. These p-gons form the regular tessellation {p,q} by p-sided polygons with q of them meeting at each vertex. Figure 3 below shows the tessellation {6,4} (with a central group of fish on top of it). As can be seen, Escher essentially used the {6,4} tessellation in Circle Limit I.
Moreover, I wanted the replication algorithm to build the pattern outward evenly in "layers", so that there would be no jagged edges. At that time, my colleague Joe Gallian had some undergraduate research students who were working on finding Hamiltonian paths in the Cayley graphs of finite groups [Gallian]. I thought that their techniques could also be applied to the infinite symmetry groups of Escher's Circle Limit designs. This turned out to be the case, although we found the desired paths in two steps.
The first step involved finding a Hamiltonian path in the Cayley graph of symmetry group of the tessellation {p,q}. This was done by David Witte, one of Gallian's research students. John Lindgren, a University of Minnesota Duluth student, implemented the computer algorithm, with me translating Witte's path into pseudo-FORTRAN [Dunham1].
The Cayley graph of a group G with a set of generators S is defined as follows: the vertices are just the elements of G, and there is an edge from x to y if y = sx for some s in S. Technically, this defines a directed graph, but in our constructions, the inverse of every element of S will also be in S, so for simplicity, we may assume that our Cayley graphs are undirected. As an example, the symmetry group of the tessellation {p,q} is denoted [p,q]. That symmetry group is the same as that of the tessellation by right triangles with angles pi/p and pi/q. The standard set of generators for the group [p,q] is {P,Q,R}, where P, Q, and R are reflections across the triangle sides opposite the angles pi/p, pi/q, and pi/2, respectively, in one such triangle.
There can be one-way or two-way Hamiltonian paths in the Cayley graphs of symmetry groups of hyperbolic patterns [Dunham3]. However, one-way paths are sufficient for our algorithms, so in this article "Hamiltonian path" will always denote a one-way Hamiltonian path.
There is a useful visual representation for the Cayley graphs of the groups [p,q], and thus for their Hamiltonian paths. A fundamental region for the tessellation {p,q} is a triangle that when acted on by the symmetry group [p,q] has that tessellation as its orbit. This fundamental region can be taken to be a right triangle lying on the horizontal diameter to the right of center, with its pi/p vertex at the center of the disk. This triangle is labeled by the identity of [p,q]. Each triangle of the tessellation is then labeled by the group element that transforms the fundamental region to that triangle. Thus each triangle represents a group element. To represent an edge in the Cayley graph, we draw a line segment connecting the centers of any two triangles sharing a side. Thus, there are three line segments out of each triangle, each representing the reflection across one side.
Figure 3 shows a Hamiltonian path in the Cayley graph of the
group [6,4] with the standard set of generators.
The heavy line segments, both solid and dashed, represent the Cayley graph;
the light lines show the triangle tessellation.
The Hamiltonian path consists of the solid line segments.
Essentially the same path works for [p,q] in general,
though slight "detours" must be taken if p = 3 or q = 3
[Dunham3].
|
|
|
|
The second step then consisted of finding Hamiltonian paths in "Cayley coset graphs". Conceptually, we form the cosets of a symmetry group by the stabilizer H of its super-motif. Then, by analogy with ordinary Cayley graphs, we define the vertices to be the cosets, and say that there is an edge from xH to yH if sxH = yH for some s in S.
Again, there is a useful visual representation for these coset graphs.
The vertices correspond to the p-gons in the
tessellation {p,q}.
The central p-gon is labeled by H, and any other p-gon is
labeled by xH, where x is any element of the symmetry
group that maps the central p-gon to the other p-gon.
In this case, the generating set S is composed of words in
the generators of the symmetry group.
For each side of the central p-gon, there is at least one word
that maps the central p-gon across that side.
Much as before, we represent edges of the graph as line segments
between the centers of the p-gons.
Figures 5 and 6 show the coset graph of a subgroup of [6,4].
Again, the graph edges are the heavy lines, either solid or dashed,
and the light lines show the {6,4} tessellation.
The solid graph edges in Figure 5 show a Hamiltonian path.
|
|
One shortcoming of this method is that the Hamiltonian path must be stored in computer memory. This is not a serious problem, since the path can be encoded by small integers. That method essentially works by forming ever longer words in the generators from the edges of the Hamiltonian path. The transformations were represented by real matrices, which led to roundoff error after too many of them had been multiplied together to form the current transformation matrix. This was a more serious problem.
Both problems were cured by using recursion.
What was required was to find a "Hamiltonian tree" — or more
accurately, a spanning tree — in the coset graph.
The tree is traversed on the fly by recursively transforming
across certain sides of the current p-gon.
Those sides are determined by fairly simple combinatorics
[Dunham2] (there is an error in the recursive algorithm in [Dunham1]).
With this method, the path from the root (central p-gon) to
the current p-gon is stored automatically in the recursion stack.
Also, the recursion depth never gets deeper than a few dozen, so
there is no noticeable roundoff error from multiplying transformations.
The solid graph edges in Figure 6 show a spanning tree in the coset
graph of [6,4].
|
|
Other researchers have used different methods to generate a set of words in the generators of hyperbolic symmetry groups in order to replicate repeating hyperbolic designs. One method is to keep track of the transformations generated so far and iteratively add new transformations by multiplying all the previous transformations by the group generators, discarding duplicates. Then the desired pattern is generated by applying the final set of transformations to the motif. The techniques of automatic groups have been used to efficiently generate non-redundant sets of words. Silvio Levy has used this technique to create a computer rendition of Escher's Circle Limit III [Levy].
Like many mathematicians, I was immediately enthralled by M. C. Escher's intriguing designs when I first saw them, more than 30 years ago. Several years later when I became involved with computer graphics, that seemed like an obvious medium to use to produce Escher-like designs. When discussing the symmetry groups of Escher's hyperbolic patterns with Joe Gallian, it occurred to me that Hamiltonian paths could be used as a basis for an algorithm to generate such patterns. At this point everything had come together and I could not resist the temptation to regenerate Escher's hyperbolic patterns with a graphics program. As described above, the students and I achieved this goal.
Having gone to the trouble of implementing a hyperbolic pattern program, I could not resist the further temptation of creating more hyperbolic patterns. I found inspiration in Escher's Euclidean repeating patterns. In constructing my patterns, I noticed myself paying attention to aesthetic issues such as shape and color. More of these hyperbolic designs can be seen in my chapter in the recent book Escher's Legacy [Schattschneider2]. When designing these patterns, I think of myself as working in the intersection of interesting mathematics, clever algorithms, and pleasing art.
[Coxeter1] Coxeter, H. S. M., "Crystal symmetry and its generalizations", Royal Society of Canada (3) 51 (1957), 1-13.
[Coxeter2] Coxeter, H. S. M., "The non-Euclidean symmetry of Escher's Picture `Circle Limit III'", Leonardo 12 (1979), 19-25, 32.
[Bool] Bool, F.H., Kist, J.R., Locher, J.L., and Wierda, F., editors, M. C. Escher, His life and Complete Graphic Work, Harry N. Abrahms, Inc., New York, 1982. ISBN 0-8109-0858-1
[Dunham1] Dunham, D., J. Lindgren, and D. Witte, "Creating repeating hyperbolic patterns", Computer Graphics, 15 (1981), no. 3, 79-85.
[Dunham2] Dunham, D., "Hyperbolic symmetry", Computers and Mathematics with Applications, Part B 12 (1986), no. 1-2, 139-153.
[Dunham3] Dunham, D., D. Jungreis, D. Witte, Infinite Hamiltonian paths in Cayley digraphs of hyperbolic symmetry groups, Discrete Mathematics, 143, 1995, 1-30.
[Gallian] Gallian, J., On-line bibliography of the Duluth Summer Research Programs supervised by Joseph Gallian, http://www.d.umn.edu/~jgallian/progbib.html
[Goodman-Strauss] Goodman-Strauss, Chaim, "Compass and straightedge in the Poincaré disk", Amer. Math. Monthly, 108 (2001), no. 1, 38-49.
[Greenberg] Greenberg, Marvin, Euclidean and Non-Euclidean Geometries, 3rd Edition, W. H. Freeman and Co., 1993. ISBN 0-7167-2446-4
[Levy] Levy, Silvio,. Escher Fish, at: http://geom.math.uiuc.edu/graphics/pix/Special_Topics/Hyperbolic_Geometry/escher.html
[Roosevelt] The letter of December 29, 1958 from H. S. M. Coxeter to M. C. Escher, from the Roosevelt collection of Escher's works at The National Gallery of Art, Washington, D. C.
[Schattschneider1] Schattschneider, Doris, A picture of M. C. Escher's marked reprint of Coxeter's paper [1], private communication.
[Schattschneider2] Schattschneider, Doris, and Michele Emmer, editors, M. C. Escher's Legacy: A Centennial Celebration, Springer Verlag, 2003. ISBN 3-540-42458-X