CS798 Lecture notes

Lecture 1: Introduction to ornament

The main lecture consisted of a general introduction to the world of ornamental design. I discussed common characteristics of ornament and some of the history. I then made some observations about why we seem predisposed to cover surfaces with ornament, and why we're in a good position to study the subject today.

Notes:

• A lot of the content of the lecture appears in the first few sections of my PhD thesis.
• My thoughts on the human compulsion to create ornament have evolved since 2002. My thesis focuses primarily on an explanation drawn from psychoaesthetics. I have since tried to incorporate some additional ideas from gestalt psychology and information theory. A good graphics-oriented introduction to the former is Frédo Durand's 2002 SIGGRAPH course. I haven't found much published on the relationship between art and information theory (there's probably an opportunity to do some new writing here), but this essay by Jim Bumgardner has many overlaps with some of my thinking on the subject.
• As always, I strongly encouraged everyone to listen to streaming versions of Ramachandran's 2003 Reith lectures, particularly "The Artful Brain" and "Purple Numbers and Sharp Cheese".
• A standard resource for examples of ornament is Owen Jones's The Grammar of Ornament. More examples, together with mathematical analysis, can be found in Symmetries of Culture. See the references page for pointers.
• Some ideas were drawn from the following additional sources:
  • Archibald Christie. Traditional Methods of Pattern Designing. Oxford University Press, 1929.
  • E.H. Gombrich. The Sense of Order: A Study in the Psychology of Decorative Art. Phaidon Press Limited, second edition, 1998.

Lecture 2: Introduction to symmetry theory

Topics:

• Cyclic and dihedral groups, frieze groups, wallpaper groups
• Flowcharts for determining frieze and wallpaper groups (from Symmetries of Culture)
• Fundamental regions
• The crystallographic restriction

Notes:

• One possible introduction would be Section 2.2 of my thesis. A very accessible introduction to symmetry is David Farmer's Groups and Symmetry: a Guide to Discovering Mathematics.
• Information about planar symmetry groups can be found just about anywhere on the web. Just do a web search for "symmetry group" or "wallpaper pattern", etc. The wikipedia entries on the subject might be a good starting point.
• John Conway has a very amusing classification of the frieze groups in terms of footprints. Be sure to practice these -- they'll be on the final exam!
• The appendices of Symmetries of Culture contain lovely proofs of the classification of planar isometries and of the frieze groups.
• Kali is an absolute classic in the world of Java applets. It lets you draw symmetric pictures in the finite, frieze, and wallpaper groups. Play with it for a while to strengthen your intuition.
• A really nice piece of recent software is Tess, by Pedagoguery Software. It draws pictures using the planar symmetry groups (or the Heesch tilings, more on them later), and is very fully-featured.
• Note that Kali (and many other tools) don't use the international crystallographic symbols for the symmetry groups. Kali uses Conway's very reasonable "orbifold notation". Rather than delve into orbifolds this term, I'm just going to stick with the standard notation.
• Victor Ostromoukhov wrote an excellent article that provides computer scientists with useful conceptual tools for generating symmetric drawings. It's called "Mathematical Tools for Computer-Generated Ornamental Patterns".

Lecture 3: Other forms of symmetry

Notes:

• The material on counterchange symmetry came primarily from Section 8.2 of Grübaum and Shephard. Symmetries of Culture also has a lot to say on the subject, including flowcharts for determining a pattern's 2-colour symmetry group.
• G+S also discuss n-colour symmetry in Chapter 8 of their book. Some additional material came from Coxeter's paper "Coloured Symmetry", which appeared in M.C. Escher: Art and Science (North-Holland, 1986). The topic of coloured symmetry quickly gets into serious group theory.
• The presentation of two-sided symmetry came from Chapter 5 of Shubnikov and Koptsik's Symmetry in Science and Art (Plenum Press, 1974). Another good presentation is Peter Cromwell's paper "Celtic knotwork: Mathematical art" (The Mathematical Intelligencer, 15(1):36-47, 1993). This paper was distributed in class, anticipating the coming lecture on Celtic knots.

Lecture 4: Celtic knotwork

• I began with some historical examples from the Book of Kells, the Lindisfarne Gospel, and Jones's Grammar of Ornament. Images from the first two can easily be found via web searching. Some images also appear on wikipedia.
• I went through the most popular knotwork construction technique, based on J. Romilly Allen's "modified plaitwork" approach. This approach was refined by George Bain and later by his son Iain Bain. Many good examples appear in George Bain's Celtic art: the methods of construction (Dover, 1973). The book is fun to read -- Bain grumbles often about the mistakes in previous reproductions of Celtic art, even Owen Jones. ("The above two examples show gross travesties of Pictish art in publications that have been the chief sources of information available to students and others in the libraries of the universities and art colleges of the civilised world, for the past fifty years.")
• More recently, Andrew Glassner wrote three columns for IEEE Computer Graphics & Applications. (September 1999, November 1999, January 2000). The first of these is a recapitulation and implementation of Bain's work, and provides more than enough details to complete the assignment, including suggested curves for tiles.
• The primary inspiration for the lecture was "Celtic knotwork: mathematical art" by Peter Cromwell (The Mathematical Intelligencer 15(1):36-47). The paper introduces Bain's method, and discusses some of the mathematical properties of Celtic friezes, most importantly which of the two-sided frieze groups can (and do) arise naturally.
• Mercat's method (see also the English version with implementation by Steve Abbott) is a generalization of Bain's method that works on an arbitrary tiling instead of a square lattice.
• I briefly covered Cameron Browne's RIDT'98 paper "Font Decoration and Automatic Mesh Fitting", which filled arbitrary letterforms with knotwork. Some images appear here and here.
• Matthew Kaplan (no relation) has also done some research on Celtic knotwork. One paper uses Mercat's method to produce novel knots and decorates those knots with zoomorphs (stylized animal forms). A later paper tries to construct Celtic knots over 3D meshes.
• I closed by mentioning briefly other forms of Celtic art, namely spiral designs and key patterns. From a computer graphics point of view, there's lots of research that can be done in these areas. For key patterns, I'll mention Iain Bain's book Celtic Key Patterns (Constable, 1993), which also reproduces some earlier work by J. Romilly Allen. Doug Dunham also has a short paper about hyperbolic key patterns. Finally, there's a reproduced page from a Celtic manuscript on display in the bottom floor of the CEIT building.

Lecture 5: Introduction to tiling theory

• Almost all the material from this lecture was reproduced (or lightly adapted) from Chapters 1 and 3 (and a very small amount of Chapter 6) of Tilings and Patterns. See in particular Sections 1.1, 1.2, 1.3, 1.4, 3.1, and 3.2.
• There were some questions related to some of the definitions I presented in class. First, the definition of "normal tiling" rules out tiles with holes and tilings where tiles intersect in multiple disjoint curves. But such tilings seem reasonable in lots of situations. I asked Branko Grünbaum about this. he replied that at the outset, they felt that many theorems would need to assume that intersections are connected, so they may as well make that be the default and vary from it when possible. He says, "If I had to start from scratch, I would probably not include this requirement in the definition of normality, but invent a snappy term for this property. 'Normal' would then mean just the existence of a common in- and circum-radius."
• I defined a "tiling vertex" as any point arising as the intersection of two tiles. But soon after, we discovered that tilings can contain tiling vertices that aren't defined by any two tiles' intersection. Going back to the source, Grünbaum and Shephard say that if a finite set of tiles intersects in a point, that point is a tiling vertex. Without the restriction that two tiles define a tiling vertex, we'll get all of them.
• I defined an "edge-to-edge" tiling as a tiling by polygons where the tiling vertices and edges are identical to the polygonal corners and sides. That definition stands, though in class I was a bit confused about my working example. It turns out that no, there's no tiling by the L-triomino that's edge-to-edge. For such a tiling to be edge-to-edge, the vertex of the L with a 270 degree angle would have to meet two other copies of the tile, which is impossible.
• I mentioned that the search for k-anisohedral tilings is still a topic of active research. See in particular the websites maintained by John Berglund and Joseph Myers. They both search for anisohedral tilings with different properties.

Lecture 6: Polygonal tilings

• I gave the flag-transitive definition of regular tilings and showed that the only possible Euclidean regular tilings are 3⁶, 4⁴, and 6³.
• I discussed edge-to-edge tilings by regular polygons. There are 17 species of vertex, and 21 types (where order is taked into account). Only 11 of those species can arise in tilings of the plane. When every vertex of must be the same type, exactly 11 tilings (the Archimedean tilings are possible). They happen to be uniform.
• I defined star polygons and presented the two notations from the book. I showed some examples of edge-to-edge and uniform tilings by star polygons. Note that "uniform" in this context refers only to the tiling vertices, not the larger set of tile corners.
• I showed some interesting non-edge-to-edge tilings by squares, and others by equilateral triangles. The interesting thing here is to incorporate multiple sizes of tiles, and ensure that each distinct size is in its own transitivity class (i.e., that the tiling is equitransitive). Doing this with lots of different square sizes can harness "squaring the square" solutions.
• I closed with one of my favourite open problems in geometry, that of finding a uniformly-bounded tiling of the plane where every tile has (at least) fivefold rotational symmetry. Many alternatives to this problem are easily solved (non-uniformly-bounded tiles, non-Euclidean geometry). See problem C12 of Croft, Falconer and Guy's Unsolved Problems in Geometry or Danzer, Grünbaum and Shephard, Can all tiles of a tiling have five-fold symmetry?, Amer. Math. Monthly 89 (1982):568-585. It should be easy to show that the tiling could not be monohedral. It might be interesting to attempt proving that the tiling cannot be n-hedral for any finite n.

Lecture 7: Theory of isohedral tilings

• I discussed monohedral polygonal tilings with regular vertices, and showed that the Laves tilings are the canonical examples. They are the duals of the Archimedean tilings (and so there are eleven types, with one occuring in two enantiomorphic forms).
• I introduced some basic concepts from the topology of tilings. I talked about topological equivalence and combinatorial equivalence and homeohedral tlings.
• Every isohedral tiling is clearly homeohedral, so the tiling's topology type is a good initial classification. Of course, many fundamentally different isohedral tilings may share a single topology type, so we need a finer classification.
• In any isohedral tiling, every tile is related to its neighbours in the same way. In other words, if I blindfolded you and dropped you into the tiling at random, you couldn't tell which tile you were in because the world looks the same from every tile.
• Given an isohedral tiling, we can derive an incidence symbol, a combination of a tile symbol and an adjacency symbol. This symbol captures all information about the tiling except for the incidental shapes of the edges. Two tilings are of the same isohedral type if their symbols can be made to correspond under a trivial relabeling.
• We can enumerate all possible incidence symbols, eliminate those that don't correspond to tilings, and discard equivalent symbols. We're left with exactly 93 isohedral types. Only 81 of them can be realized by marked tiles. The marked tiles are the interesting ones for ornamental design, since we can modify the shapes of the edges.

Lecture 7: Implementation of isohedral tilings

• We need to understand the range of possible tiling edge shapes. From an incidence symbol, we can derive the internal symmetries of each edge. We then know whether the edge has symmetry c₁ (a J edge), d₁ (a U edge), c₂ (an S edge), or d₂ (an I edge). We must then take into account the fact that if an edge labeled a meets an edge labeled b, those edges are just transformed versions of the same shape. Putting all these relationships together, we can factor the edge shapes into a minimal non-redundant set.
• The tiling vertices are bit trickier because they're interdependent. But by examining the symmetry group and incidence symbol, we can derive tiling vertex parameterizations that do a reasonable (but imperfect) job of capturing the range of tiling vertex configurations. After producing these parameterizations, Branko Grünbaum pointed me at very similar constructions by Heesch and Kienzle, published in Flächenschluss in 1963. Their parameterizations cover a subset of the isohedral tilings.
• I talked about k-colouring of tilings (which has nothing to do with the usual notion of graph colouring) and perfect colouring. A discussion of perfect colourings is given in Chapter 8 of Tilings and Patterns. See also G.C. Shephard, "What Escher Might Have Done", published in Michele Emmer, Ed., M.C. Escher: Art and Science (Elsevier, 1986). That paper includes perfect colourings of Escher's fish (drawing #20) tiling with two, four, five, six, and thirteen (!) colours.
• I spent a while demonstrating the implementation, showing how factoring out redundancy early can make it easy to keep all symmetric copies of a feature consistent. I showed how to draw the tiling by assembling aspects into a translational unit, and how to apply colours at rendering time.

Lecture 8: Escher and his periodic tessellations

• Escher developed an extensive "layman's theory" of tilings. He wasn't trained in mathematics, but had a profound intuition and his layman's theory is quite extensive. Visions of Symmetry presents not just an explanation of the theory, but the original pages from Escher's notebook. How's your Dutch? Tilings produced by his layman's theory are isohedral, which makes the parameterization of isohedral tilings from the previous lecture an ideal framework in which to create new Escher-like tilings.
• Then, I naturally spoke at length about the Escherization algorithm. This work appeared in a SIGGRAPH 2000 paper and was polished up a bit for my thesis. Escherization turns shapes into isohedral tilings via an optimization process over the space of isohedral prototiles. The objective function is an L² metric for comparing two polygons.
• Escher also produced many multihedral tilings. Dihedral Escherization handles the dihedral case nicely by splitting isohedral tiles with an extra path. The justification for splitting this way comes from Delgado Friedrichs, Huson and Zamorzaeva, "The classification of 2-isohedral tilings of the plane", Geometricae Dedicata 42:43-117, 1992.
• I presented some ideas for future work on Escherization, which provoked discussion in the class. Some of these ideas could make excellent projects for the course. (Hopefully, I'll put together a separate page of project ideas.)

Lecture 9: Metamorphoses and Deformations

• I begin by classifying the devices used by Escher to make transitions. This is taken from Chapter 5 of my thesis. I don't have much to say about four of them (Crossfade, Abutment, Realization, and Growth), though it's interesting to contemplate whether any of them could be incorporated into a design tool for metamorphoses.
• I say more about Sky and Water designs. In my paper "Dihedral Escherization" (GI'2004), I show how to construct these designs as an extension to the basic Escherization algorithm. To do so, you need to optimize over a special subset of the isohedral tilings. Dress classifies the needed tilings in "The 37 combinatorial types of regular 'Heaven and Hell' patterns in the Euclidean plane", Michele Emmer, Ed., M.C. Escher: Art and Science (Elsevier, 1986).
• I had the most to say about Interpolation, the device that's also used in parquet deformations. The key reference for parquet deformations is Chapter 10 of Hofstadter's Metamagical Themas: questing for the essence of mind and pattern (Bantam, 1986).
• I reduced the general problem of interpolation to the question of interpolating between two isohedral tilings. Even then, there is a hierarchy of problems with varying difficulties. Easiest is to transitions between two tilings with congruent tiling vertices. The general case is most difficult, but perhaps not impossible.
• We can also differentiate between spatial animation (where the tilings evolve over one axis of space) and the usual temporal animation. It seems like temporal animations would be a bit easier to deal with, since in the spatial case individual tiles must fight each for space other as they're evolving.
• There are some interesting examples of animated tilings, both spatial and temporal, on the web.
  • Makoto Nakamura has a page of lovely temporal animations of tilings
  • Bulli is a popular tool for making designs in the style of parquet deformations.
  • This page has some additional information about parquet deformations, including some examples which I believe were created by John Sharp.
  • Alvy Ray Smith designed a lovely parquet deformation sculpture in glass.
  • I found it amusing to do a Google image search on the phrase "parquet deformations".

Lecture 10: Nonperiodic tilings

Many lovely examples of these and other tiling-related topics can be found in the tiling section of the Geometry Junkyard.

• I start with some spiral tilings. The material in this section is taken directly from Section 9.5 of Tilings and Patterns. In fact, the cover of the book features one of the spiral tilings from this section. The Voderberg spiral is particularly interesting because the prototile can be completely surrounded by only two copies of itself, resolving a previously open problem in geometry.
  
  I remember being at a party in a nightclub in Seattle some years ago in which they projected one of these spiral tilings (the cover image, I believe) as part of the light show. I was, needless to say, deeply impressed.
• I then move on to reptiles, which are covered in Section 10.1. There are lots of interesting variations on reptiles, including fractal reptiles. As with spiral tilings, there are still some interesting open questions that would make for a nice bit of deep thinking in geometry.
• Next, I move to overlay tilings. A good, simple introduction is Doug Zongker's paper. It also references the relevant literature, most importantly the paper by Stampfli. Overlay tilings provide a simple way to generate ordered but irregular tilings by simple polygons. They'd be great in a decorative context (e.g., tiling your floor).
• At this point, I formally define aperiodic tiles. It's not immediately obvious that aperiodic tiles exist at all, and earlier in the twentieth century Hao Wang conjectured that they didn't. In 1966 the first set of aperiodic tiles (containing 20426 tiles!) was exhibited, based on what are now called "Wang tiles" in honour of Hao Wang.
  
  What's amazing is that Wang tiles are a model of computation (they're Turing complete). In other words, for any computer program there exists a set of Wang tiles that can tile the plane if and only if the program halts. This guarantees that the question "does this set of shapes tile the plane?" must be formally undecidable in the general case.
• There are a couple of recent applications of Wang tiles in computer graphics. See in particular the papers by Cohen et al. and Fu and Leung. I find the last to be particularly interesting -- it harnesses a loose square parameterization of any surface called the polycube map. I see lots of potential for these in ornamental design on surfaces.
• Finally, I highly recommend the book Diaspora by Australian science fiction author Greg Egan. It's very heavy on math and physics, but fascinating. Where else will you find a whole chapter about a lifeform based on Turing machines, Wang tiles, and Fourier analysis? It's fun to browse Egan's website -- it's full of essays, explanations of the math behind his books, Mathematica diagrams, Java applets, and so on.

Lecture 11: Aperiodic tilings

However, this material is absolutely beautiful and most deserving of study. Everybody with an interest in math and art should be introduced to the Penrose tiles and get an understand of how they work.

This material is mostly taken from Chapter 10 of Tilings and Patterns. You might also want to take a look at the Penrose tiling section of the Geometry Junkyard. Be sure to read the article on toilet paper plagiarism! And make sure to carefully study the cartoon Bob the Angry Flower Goes Through Customs!

I'm pretty happy with the quality of the slides I created to demonstrate the aperiodic tile sets I discussed. Here's a PDF of the slides to refresh your memory and in case anyone out on the web can use them for teaching. Of course, when I make slides I just put the pictures on them, and speak from notes. No bulleted lists here!

• As a warm-up, I start with Robinson's aperiodic set R1 of six tiles. I prove they must assemble into 3x3 blocks in a fixed set of ways, then suggest how this process may be carried out for ever larger square blocks of tiles. I also say briefly why all these tilings must be nonperiodic. The payoff is the observation that the protusions on the tilings can be interpreted as an infinite hierarchy of overlapping suqares of different sizes.
• I the proceed to Penrose's first aperiodic set, P1. I show how the deflation process works. Presumably, deflation can be carried out an infinite number of times to tile the whole plane. Is that so? At this point we truly need some extra machinery to explain how that could be possible. Therefore, I invoke the extension theorem from Chapter 3 of Tilings and Patterns. The extension theorem is like a theorem about limits: if a set of tiles admits arbitrarily large patches of tiles, then it tiles the whole plane. If anything deserves to be called the "fundamental theorem of tilings", this seems like a good candidate.
  
  Because this process can be carried out in reverse (tiles can be grouped together and recomposed into large copies of themselves in a unique way), we can argue that any tiling by P1 is necessarily nonperiodic.
  
  It's worth reading Penrose's informal article Pentaplexity, which explains his inspiration for P1.
• From P1 I move to P2 (kites and darts), and P3 (thin and thick rhombs). I discuss the aperiodicity of these two sets, and outline one of my favourite proofs from tiling theory: tilings from P2 must be nonperiodic, because the limit of the ratio of kites to darts goes to the golden ratio as you repeatedly deflate. But this ratio must be rational for any periodic tiling!

• As Grünbaum and Shephard point out, the matching conditions on P2 and P3 (and P1 for that matter) can be represented by suitably chosen edge shapes. I use that fact in my research to do Escherization on Penrose tilings. The results are of low quality -- it's hard to get good shapes out of P2 and P3. The necessary parameterizations are given in Section 4.6.4 of my thesis. You can also play with a Java applet I wrote for manipulating Penrose tile shapes.
• There are many wonderful ways to draw a patch of Penrose tiles. Simply putting down a tile and attaching tiles to it is likely to run up against an inconsistency eventually; your drawing algorithm needs to be global. The deflation rules for P2 provide a good way to do this. In preparing this lecture, I realized that you can apply the deflation rules very easily, without worrying about overlaps at all -- each tile produces two darts under deflation, and you simply keep the left-hand one. This is much simpler than any other technique I've implemented in the past.
• I finished up with some decorative applications of Penrose tiles. There are a few more that I want to show but don't have images for, or want to show but only after introducing more math. There is a great deal of potential for the ornamental use of Penrose tiles.
• In discussing aperiodic tilings, we got from the original 20426 tiles down to a set of two that tile only nonperiodically. The natural question is whether a single shape can be an aperiodic tile set. Very little is known about this problem, which I recommend as a wonderful unsolved problem in geometry. It's fairly easy to see that such a shape exists in 3D.

Lecture 12: Further properties of Penrose tiles

• I basically cover Section 10.5 of Tilings and Patterns, which demonstrates the local isomorphism property of P2 via the Cartwheel tiling. We cover the following facts about P2 (which pretty much carry over to the other Penrose sets too):
  • Inflation preserves symmetries of patches of tiles.
  • Except for an anomalous patch of seven tiles at the centre, every tile in the cartwheel tiling is contained in a patch with d₅ symmetry.
  • In every tiling by kites and darts, every point in the plane is contained in an ace (one of the seven vertex configurations that can occur in P2 tilings.
  • In every P2 tiling, every tile lies in a cartwheel of every size.
  • Any arbitrarily large patch of tiles that occurs in a P2 tiling occurs infinitely often in every P2 tiling.
• I show two remarkable methods for generating P3 tilings by thin and thick rhombs. For the first one, observe that the rhombs in any P3 tiling line up into five distinct families based on edge directions. These families can be summarized by five families of parallel lines. Note that the spacing of the lines is given by a "Fibonacci sequence", a kind of nonperiodic tiling of the line.
• What's amazing is that the reverse is true as well: given five evenly-spaced families of parallel lines, you can construct the dual (in the sense of the overlay tilings of Lecture 10) and get a P3 tiling. De Brujin called this the "pentagrid method". Jie found an excellent recent article by Robert Austin that shows all these properties very effectively.
• Finally, I talk about the "lattice projection" method. In this method, you slice through a high-dimensional integer lattice and project features of the lattice down onto the cutting hyperplane orthogonally to produce tiles. When the cutting plane is oriented just so, the result is a nonperiodic tiling. This is the method demonstrated by Quasitiler (the online application doesn't work, but the website still contains a lot of information). I also discovered that someone had reimplemented Quasitiler in the context of a Java-based screensaver. Be sure also to see Greg Frederickson's web page about his rhombic coffee table, which is related to P3.
• For more information on the algebra of Penrose tilings, see Marjorie Senechal's book Quasicrystals and Geometry.

Lecture 13: Euclidean and non-Euclidean geometry

• I open by stating Euclid's postulates (expressing the parallel postulate in its familiar modern form as Playfair's postulate). I use this as a way to say what the problems were that led people to study Euclid's work more carefully with the tools of "modern" mathematics. I point out that the terms "point" and "line" are best left simply undefined (Euclid provided rather fanciful definitions that don't add any rigour). Also, the relationships of "incidence", "betweenness" and "congruence" can be left undefined; their behaviour will be constrained by the axioms.
• If all these things are undefined, how do we know what we're talking about? We can do math formally, but Euclid clearly had a mental picture of an infinite 2D plane when he gave his axioms. In modern terms, we speak of specifying an interpretation for a formal system in which the undefined terms are concrete spaces and relations, and the axioms are statements. If the axioms are indeed true statements in the interpretation, that interpretation is called a model.
• Models tell us a lot about formal systems. I give two examples.
  • Say you have two formal systems F and G, and G is a model for F. If you believe in the consistency of G, you must then believe in the consistency of F, for any inconsistency in F could be passed through the model and become a proof of G's inconsistency! This is called relative consistency.
  • Say you have a formal system F and some statement s that you want to show is provable from F. If you exhibit a model of F in which s is false, then it can't be provable in the formal system! Similarly, a model of F in which s is true shows that its negation is not provable. If both models exist, s is said to be independent of F.
• There are lots of models of Euclidean geometry as Euclid described it. The empty set of no points satisfies the postulates, as do lots of simple toy geometries that can be drawn as graphs (Greenberg gives some good exmaples). The model we're familiar with is the real Cartesian plane with coordinates consisting of two-tuples of real numbers. But Euclid's postulates don't force that to be the only model, even though that's what he had in mind. Many mathematicians, most notably Hilbert, offered more rigorous treatments of Euclidean geometry in which all possible models are isomorphic. Such a formal system is called categorical.
• For a long time, the parallel postulate was thought to be provable from the other four. In the nineteenth century, it was shown that you can accept a negation of the parallel postulate and arrive at a consistent geometry called hyperbolic or Lobachevskian geometry. It was proven (relatively) consistent by exhibiting a model (the Beltrami-Klein model) within Euclidean geometry.
• If you take (Hilbert's presentation of) Euclidean geometry and leave off the parallel postulate altogether, you get neutral geometry, in which you can say all true things about Euclidean or hyperbolic geometry as long as you don't make any assumptions about parallel lines. It seems natural to incorporate spherical geometry into this development, but that's not possible. The sphere doesn't play nicely with betweenness, and in any case you can prove in neutral geometry that parallels do exist (they don't on the sphere). But it's possible to reformulate the axioms of geometry to avoid this incompatibility. In College Geometry (Holt, Rinehart and Winston, 1969), David Kay presents Birkhoff's ruler-and-protractor postulates, massaged so that you can tack on any of the three possible parallel postulates at the end and obtain a consistent geometry.
• We're quite comfortable with the Cartesian plane as a model for Euclidean geometry, and it's not too much of a stretch to visualize the sphere as a model of spherical geometry (not elliptic geometry; in spherical geometry points are single points on the sphere and lines are great circles). There are several models of hyperbolic geometry, all of which have different uses.
  • The Minkowski hyperboloid model (or the Lorentz model) uses the upper sheet of a hyperboloid of one sheet defined by the equation x² + y² - z² = -1. Lines are the intersections of the hyperboloid by planes through the origin of 3D space. This model is convenient for representing rigid motions, which turn out to be expressible as 3x3 matrices. It's therefore useful for drawing symmetric pictures in the hyperbolic plane.
  • In the Beltrami-Klein model, points lie in the interior of a disk in the Euclidean plane. Lines are chords of the disk (including diameters). Obviously, we don't use Euclidean distance to measure the hyperbolic distance between two points. The advantange of this model is that it's projective -- straight hyperbolic lines are represented by straight Euclidean lines. Thus incidence and betweenness are easy to visualize, and many geometric computations become very simple. A potential disadvantage is that it's not very numericallly stable, since most information is packed near the boundary of the disk.
  • The final useful model is the Poincaré disk model. Again, points lie in a disk. Lines are now represented by circular arcs that cut the disk at right angles (including diameters). Lines are no longer straight, but the Poincaré model is conformal: the Euclidean angle between two arcs is equal to the angle between the corresponding hyperbolic lines. In some sense, this makes is most suitable for representing "shapes" accurately in ornamental contexts. Most computations are difficult in this model, so it's best to stick it at the end of a hyperbolic graphics pipeline.
• If you take Kay's axioms without the parallel postulate, you can say anything that's true in the Euclidean plane, the hyperbolic plane, or the sphere. We call this formal system absolute geometry. Any theorem of absolute geometry is automatically true in all three sub-geometries. More importantly, if you construct some shape or design using only theorems of absolute geometry, you automatically get three separate pictures. Absolute geometry can be a bit hard to visualize, because there's no good model that captures only the true facts about it. All the models we've seen are automatically models of absolute geometry, but they're misleading because they all enforce some behaviour for parallels. Furthermore, we have to work with undefined concepts. I know that I can measure distances in absolute geometry, even if I can't tell you what the distance function actually is -- that's a property of the model.
• None of these conceptual problems pose any difficulty in an implementation of absolute geometry. An implementation can follow the familiar object-oriented paradigm. The formal system with its axioms and theorems becomes an abstract interface, and the models become implementations of that interface. At runtime, we can substitute different models to get the same construction in different planes. I suggest a Java-like approach using subclassing, and a C++-like approach using template specialization. The latter is explained in more detail in my thesis.
• I give a definition for equidistant curve, and then use that to build an absolute trigonometry, which allows us to identify the relationships between triangles in absolute geometry (again, we can do this even if we don't know how to define the functions). De Tilly defines two functions: Circle(x) (represented typographically with an actual circle) and E(x). In practice, they can be defined case-by-case for Euclidean, hyperbolic, and spherical geometry. We can then use these two functions to derive trig identities for generic and right-angled triangles in absolute geometry. Remarkable stuff.

Lecture 14: Islamic star patterns

The Islamic decorative tradition spread quickly with the rise of Islamic rule in the ninth and tenth centuries. Today, remnants of that tradition can be found across southern Europe, northern Africa, the Middle East, India, and western Asia. Small pockets of artisans continue to practice Islamic art on a smaller scale.

One of the best known varieties of Islamic art are Islamic star patterns, abstract geometric arrangements of stars and other shapes. In this lecture, I discuss some techniques for producing and decorating star patterns. Much of this discussion comes from my own work. I also highly recommend the following references.

• Jay Bonner is an architectural ornamentalist who has contributed designs to some of the most important monuments of Islam. His website includes many examples of star patterns. His work has documented some remarkable star patterns with unusual combinations of stars.
• Dover publishes the plates from Bourgoin's Arabic Geometrical Pattern & Design. There are many important flaws in Bourgoin's drawings and his construction lines are suspect, but this is still a classic reference.
• The book Arabic Art (L'Aventurine) is a collection of plates from L'Art arabe d'après les monuments du Kaire by Achille Constant Théodore Emile Prisee d'Avennes (!). The drawings by Prisse d'Avennes are exquisite, and are an opportunity to glimpse back through time at Islamic art and architecture of the late 19th century.
• Jean-Marc Castéra's Arabesques: Decorative Art in Morocco is an excellent reference with drawings and photographs that explain the Moroccan style of star pattern design (more on that in the next lecture).

Many other references can be found through obvious web searches or by looking through the citations in Chapter 3 of my thesis.

Here are the specific topics I covered.

• After some brief history and examples, I explain (my interpretation of) Hankin's polygons-in-contact technique. Given a tiling, we extend rays from the centre of every edge until they intersect other rays. The whole process is controlled by a single real-valued parameter I call the "contact angle", the angle formed by rays with the tile edges from which they start. There are many other smaller details required to make this approach robust. They are given in a paper of mine.
• Once this process is defined, we can construct what I call "Islamic parquet deformations" by varying the contact angle continuously in space.
• Many star patterns feature rosettes, where stars are surrounded by irregular pentagonal arms in a characteristic way. I show two ways to construct rosettes. The first is explicit: in A.J. Lee's paper "Islamic Star Patterns" (Muqarnas 4, 1987), he gives a compass-and-straight-edge construction for rosettes inside regular polygons. In my earlier Taprats technique, I parameterize this construction to make available a family of rosette-like shapes. You can play with Taprats as a Java applet or downloadable application.
• The other way to get rosettes is to embed their structure into the underlying tiling. In my "polygons-in-contact" paper, I show that tilings that produce rosettes can be derived from simpler tilings through a transformation I call the "rosette dual". We are now left with the choice of giving the artist explicit control over rosette shapes, or giving them a smarter collection of tilings and a single design parameter. Over time, I've become more enthusiastic about the latter approach.
• We are left asking where good tilings come from in the first place. To construct insteresting star patterns, we should identify tilings that contain many regular polygons, but which may also contain other irregular shapes. In my paper "Islamic Star Patterns in Absolute Geometry", I give one possible construction technique. We place regular polygons around rotational centres of a symmetry group, scale them until they meet each other, and fill the remaining space with tiles.
• But now observe that nothing in the polygons-in-contact technique, the rosette dual, or the tiling construction relies on parallelism. Islamic star patterns could then be constructed equally easily in the Euclidean plane, the hyperbolic plane, and the sphere. In my work, I use an abstract library that lets me express the construction using the axioms of absolute geometry, so that the different Euclidean and non-Euclidean versions can then be produced "for free".
• The lecture ends with a bunch of examples of Euclidean and non-Euclidean star patterns. Some are simply rendered, and some are constructed using various computer-aided manufacturing techniques. Star patterns serve as a good example of how the computer can be used as part of the construction of ornamental objects. Ornament, which had been marginalized because of the twentieth-century popularity of modernism, has an opportunity to regain acceptance.

Lecture 15: Geometry and Islamic art wrap-up

• Further results on Islamic star patterns
  • The paper "Interlace patterns in Islamic and Moorish art" by Grünbaum and Shephard (Leonardo 25(1992)) provides an analysis of star patterns according to the restriction of a star pattern to its fundamental region. Using the fundamental region, it is possible to determine the number of transitivity classes of strands in a pattern, the symmetry groups of the strands, whether they are closed or infinite, and the number of crossings strands make with each other. This is very much an analysis technique -- no prescription is given for producing new star patterns.
  • In The Tinkertoy Computer, A.K. Dewdney presents a method for star pattern construction based on reflecting lines off of a regularly-placed grid of circles. This process can produce a useful class of star patterns, though Dewdney admits that many of the steps require significant intuition and intervention. François Dispot's Arabeske Studio is a fully featured Java applet that implements this technique.
  • Jean-Marc Castéra's approach to star patterns is based on the Moroccan tradition and is quite different than what appears above. He more explicitly recognizes the individual shapes produced in star pattern design (this is consistent with physical construction by small terracotta tiles, a technique known as Zellij). His patterns tend to use a coarse "skeleton" of |8/3| stars ("seals of Solomon") and irregular hexagons ("safts"). The spaces in the skeleton are then filled by more shapes. The pattern is usually centered around a single, many-pointed star (with as many as 96 points) instead of a periodic pattern.
• Other forms of Islamic art
  • There is an important tradition of stylized floral design in Islamic art. Some examples appear in The Grammar of Ornament. Jay Bonner has developed his own unified Islamic floral style and has used it in his architectural work (for example, the minbar of the Ka'aba).
  • Muqarnas are an idiosyncratic form of Islamic architectural ornamentation. They are a collection of small elements that act as corbelling, smoothing the transition from a ceiling or a dome to a wall. The appearance of a muqarnas vault is somewhere between a jewel and a cave full of stalactites.
  • Islamic artisans were some of history's greatest calligraphers. There are many different styles of Arabic calligraphy. Some are free flowing and can even be arranged into animal form. The most intriguing to me is square kufic, in which words are jammed into rigid square grids. Because I can't read Arabic, it's hard for me to get a sense of how immediately readable text is when set in this style. I've been told it's a bit of a visual puzzle to native readers.
• Other artistic uses of non-Euclidean geometry
  • Tony Bomford was a surveyor for the Australian government. He also produced some hooked rugs depicting hyperbolic tessellations. Doug Dunham has written a couple of papers on the subject.
  • Helaman Ferguson has incorporated non-Euclidean geometry into several sculptures, and even produced a hyperbolic quilt.
  • Irene Rousseau has created some tile mosaics of the hyperbolic plane.
  • Doug Dunham is the master of all things hyperbolic. He writes papers that adapt traditional Euclidean ornamental designs to the hyperbolic plane in a way that's compatible with the symmetries of the original. Most recently, he studied Escher's Circle Limit III and showed how to derive other hyperbolic arrangements of fish with similar properties.
  • Carlo Séquin and Jane Yen created an interactive tool for designing and manufacturing spherical Escher tilings. They used their Escher Sphere Construction Kit to reproduce some of Escher's original carved wooden spheres, some spherical adaptation of his work, and some new original tilings. They print their designs as a single unit on a Z-Corp starch printer or in pieces on a plastic FDM machine. In the latter case, they choose the radius of the sphere so that the pieces can be glued around a tennis ball!
  • Jos Leys has experimented with many different applications of symmetry and geometry to computer imagery. He recently explored many hyperbolic tessellations, some adapted directly from Escher and some newly created.

Lecture 16: Polyhedra

Polyhedra have long been an important part of mathematical art. We could argue that they don't belong in the same group as other kinds of ornament because they are 3D objects in and of themselves. But polyhedra have many properties in common with planar ornament because of their connection to spherical geometry. And they appear repeatedly in some of the same contexts. So we'll study them in this course. The first and ultimate reference for all things polyhedral is George Hart's website. It also includes links to other useful sites. Other consistently useful online sources of information are Wikipedia and Mathworld.

• I start with some history, including lots of old images of polyhedra. The slides were taken from one of the lectures in George Hart's Computer Science and Sculpture course.
• I define and discuss properties of some basic polyhedra: the Platonic solids, the Archimedean solids, the Catalan solids, and the Johnson solids. There are some nice tricks for finding coordinates for the vertices of the Platonic solids. Two tetrahedra can be inscribed in the vertices of a cube; the vertices of an icosahedron form three mutually perpendicular golden rectangles. That the Archimedean polyhedra resemble the Archimedean
• A topic close to my heart is near misses: convex polyhedra that are nearly, but not quite, Johnson solids. This is very much an open area of inquiry. What are all the near misses? For that matter, can we even furnish a reasonable definition of them? Perhaps there's some kind of measurement of the closeness of a polyhedron to Johnsonhood, and an acceptable cutoff below which solids can be considered near misses. Jim McNeill has a page that describes some near misses, and I have my own page with a few more.

There are many other systems of polyhedra that yield attractive shapes. Some feel more "classification based": define a set of properties that your polyhedra should have, and find a way to determine all polyhedra that satisfy those properties. Other techniques are more "notation based": define an open-ended notation where strings produce polyhedra, and search for interesting examples.

• Uniform polyhedra are like Archimedean solids: the vertices form a single transitivity class under the polyhedron's symmetries. But we relax the restrictions that the solid must be convex (allowing self-intersections) and that the faces must be convex (allowing star faces and "star vertices").
• Symmetrohedra are a construction technique closely related to my tiling construction technique for Islamic star patterns. (In fact, they were a first test of the general absolute geometry approach). Regular polygons are "threaded" onto the rotational axes of a polyhedral symmetry group until they mate with one another. Then take the convex hull. Many new and interesting polyhedra are produced.
• Conway notation is a symbolic method for describing symmetric polyhedra as a sequence of topological transformations on an initial, primitive polyhedron. George Hart uses Conway notation to produce interesting sculptures. The big difficulty with Conway notation is in deciding on the "right" polyhedron with a given topology. A theorem by Koebe, Andreev and Thurston guarantees that a "canonical polyhedron" exists, but gives no prescription of how to compute it. Finding a numerical technique for constructing canonical polyhedra would be a very interesting research question.
• Stellation is a generalized process of erecting new "spikes" on top of the faces of an underlying convex solid. Consider a single face plane of a convex polyhedron. Intersect it with all the other face planes to produce a stellation diagram. Selectively enabling parts of that stellation diagram leads to potentially large collections of new solids, depending on the original polyhedron. For example, the cube and tetrahedron have no stellations, the octahedron has one (the stella octangula), the dodecahedron has three, and the icosahedron has 58. The rhombic triacontahedron has hundreds of millions!
  
  A good online tool for playing with stellations is Vladimir Bulatov's Java applet. Robert Webb's Stella is pretty much the definitive tool these days. It can draw stellations and many other kinds of polyhedra, and includes great tools like the ability to generate a net.
  
  George Hart has written some great papers about how he uses stellation diagrams as a basis for placing congruent elements in a kind of tangled polyhedral sculpture. See, for example, his paper " Sculpture from symmetrically arranged planar components".
• Compounds are overlapping symmetric arrangements of polyhedra. As far as I know, there is no general theory of compounds, so the search for new models is open ended. One systematic approach is to look at polyhedra with many vertices and partition those vertices into multiple copies of the vertices of simpler polyhedra. It's easy to fit two tetrahedra into a cube this way, or five tetrahedra into a dodecahedron. But many compounds are much more sophisticated. Magnus Wenninger, a Benedictine monk and mathematical enthusiast, has built many beautiful compounds. George Hart index of VRML models contains many examples of compounds (alas, you need a working VRML viewer to see them).
• There's a nice metalwork sculpture of an elevated small truncated rhombicuboctahedron in Al Madina.

Lecture 17: Projections of polytopes, polyhedral wrap-up

Polytopes are the generalizations of polyhedra to any number of dimensions, though the term is sometimes used to refer specifically to four dimensions. It's worth taking a look at some properties of 4D polytopes and how we might construct representations of them in 3D.

Most of the images and slides used in this lecture come directly from the "Four-dimensional forms" lecture in George Hart's computer science and sculpture course. Also worth checking out are Bathsheba Grossman's website (click on "math models", for example) and David Richter's page of Zome projects. Web searching can locate many other amazing examples of Zometool sculptures.

• We can enumerate the ordinary Platonic solids via a simple argument about face angles around a vertex. Similarly, we can enumerate the regular polytopes in 4D my measuring dihedral angles of cells around an edge. There are six regular 4D polytopes. In all higher dimensions, there are only three.
• Just as we use laws of geometry to draw 2D renditions of 3D polyhedra, we can create 3D shadows of 4D polytopes. We can use orthographic or perspective projection, and orient the polytope in a number of different ways. Often we orient and project in such a way that many elements overlap in 3D space (by analogy, an orthographically projected cube may resemble a square). That's okay -- we still get interesting mathematical sculptures.
• Zometool is a wonderful toy for exploring geometry, especially projections of 4D polytopes. With enough Zometool parts available, some incredible sculptures can be produced.
• To finish, I show many examples of 20th century polyhedral sculpture, mostly taken from George Hart's slides (and including many of his own works).

Lecture 18: Remapping the plane

• Rigid motions and similarities are certainly valid transformations of the plane, but they're not interesting in this context because they really don't "do anything". All along, we've been basing our concept of congruence on rigid motions, so translating and rotating an object doesn't change it in any useful way. Scaling potentially is a little more interesting in non-Euclidean geometry. Collineations, which preserve straightness, are also more interesting, but they also can't be forced to really change a picture. They correspond roughly to tilting and foreshortening the plane in 3D, and our perceptual systems correct for that too easily.
• It's more exciting to investigate conformal maps, which only preserve angles. As with our discussion of the Poincaré model of hyperbolic geometry, we can argue that conformal maps do a reasonable job of preserving shape. However, there is a much wider variety of non-trivial conformal maps. Many arise by treating the plane as a complex plane and considering functions that map complex numbers to complex numbers.
• Circular inversion reciprocates every point in the plane along a radius of a given circle. It swaps the interior and exterior of the circle, and exchanges the centre of the circle with the point at infinity. It turns a periodic pattern into a pattern that diminishes in size to a limit point at the centre of the circle. Circular inversion forms the basis of the geometry of the Poincaré disk, and provides the connection between the disk and the half-plane model (via an inversion in a circle tangent to the half-plane). Circular inversion pops up occasionally as a kind of fractal. George Hart suggests it as a way to produce interesting sculptures by inverting polyhedral arrangements in spheres.
• Another wonderful transformation of the plane is the Anti-mercator projection. It can be expressed as exponentiation in the complex plane. This function transforms a horizontal stripe of width 2π to a radial picture that takes up the whole plane. Horizontal lines become radial lines; vertical lines become circles; general lines become logarithmic spirals. Anti-mercator projection works very well with periodic patterns, as long as they're moved so that the vertical vector of length 2π is a translational symmetry of the original pattern. Escher used this projection several times in his work, for example in Snakes (his last print) and Butterflies.