CS 898: Tilings and Computation

About the course

Tiling theory, the study of shapes that cover the plane with no gaps and no overlaps, is a fascinating subject that draws ideas from many areas of mathematics and computer science. Results in tiling theory are interesting as advances in mathematical research. Many results also transfer over into applied domains of computer science, particularly computer graphics. And of course, the practice of tilings has numerous decorative applications in art, architecture, and design.

After I give a few preliminary lectures laying out an introduction to tiling theory, we'll survey research from across the topic, from mathematics to computational geometry to computer graphics. We won't restrict attention to the newest papers only—it's not like there's a big annual conference where all the top tiling-theoretic work is published. We'll reach back into the 20th century when appropriate, and we'll occasionally leave the bounds of CS and wade into mathematics papers (without getting too deep into the abstract realms of pure math).

Note for CS graduate students: Because this course will cover both theoretical and applied topics, you can count it towards either the "Graphics and User Interfaces" or "Algorithms & Complexity" areas of the MMath or PhD Comp I requirements (but not both!).

Student responsibilities

Here's a tentative marking scheme for the course, with some preliminary details about each of the categories. The exact weights and details are subject to change before the start of the term.

The course does not include regular assignments or a final exam.

Readings and Resources

Show and Tell

The goal of the show-and-tell is to introduce the class to an interesting tiling in a short presentation (roughly 10 minutes). The tiling can come from just about anywhere, but ideally satisfies the following criteria:

• It's visually and/or historically interesting
• It's mathematically interesting
• It can be found in the real world somewhere (it's not just a drawing in a math paper; it can be found on the side of a building, made into paving stones, etc.)

The intention is not that you should comb through published papers looking for tilings, and the talk doesn't have to be particularly technical. I'd rather you think back to a tiling you saw out in the world, or that you were aware of from architecture or design. As a canonical example, consider the use of the pinwheel tiling on the façades of Federation Square in Melbourne, Australia. Who knows: really interesting examples might inspire ideas for final projects.

Here are some suggested points to cover in your presentation (you don't have to address them all):

• What is the tiling? Where is it in the world? What's its history as a real-world object?
• Why do you find it visually interesting? Is it an especially good design for the place where it's used?
• At a high level, what's the mathematical structure of the tiling? What makes it mathematically interesting? Did they have to bend the mathematical rules at all to make the tiling work in a real-world setting?
• Do something with the tiling. A natural starting point would be to write a short piece of software that draws the tiling. If the tiling is part of a family of variations that can be explored interactively, add some interactivity to the software. Or maybe create your own artwork inspired by the tiling, using your favourite real-world artistic medium.
• Make us do something with the tiling. Feel free to devise a (short) activity based on the tiling. If that requires students to bring any special supplies to class, you should tell us in advance.

You do not need to request a particular tiling in advance—just decide on the day when you'd like to present (and brace yourself for the possibility that someone will go before you and choose the same tiling).

Paper Presentation

You must select a paper related to the themes of the course, and give a presentation about that paper to the class. You must also lead an open-ended group discussion about the paper, with the aim of engaging the class in the topic and generating ideas for new work.

There is no fixed format or template you must follow for the presentation and discussion. I suggest you aim for a presentation of around 20–30 minutes, followed by a discussion of 10–20 minutes. A 20-minute presentation is fine if that's all the time you need; you can use more, but don't exceed 30 minutes. If the discussion happens to run long, and there's time left in the class to accommodate it, that's fine. Obviously my default expectation is that you'll prepare a slide presentation and deliver it from the podium. That's not a strict requirement, but if you do something very different, it may throw other students for a loop.

The most important thing to keep in mind when preparing your presentation is that the audience will have already read the paper. Thus the context is quite different from presenting a new paper at a conference. You shouldn't plan to give a "recitation" of the paper by listing its contributions and methods in order, though of course some of the presentation should just establish what the main ideas are. You should spend time on the broader context of the work. Here are some possible things to include in your presentation. They often require you to do some research beyond the paper itself, which of course is a useful skill.

• What is the context of this paper? Who are the authors, and what's their background? Are they tiling theorists applying their work to another field? Scientists from another field doing something interesting with tiling theory? Something else?
• If this is a recent paper, what legacy did it build upon? If this is an older paper, what legacy did it leave behind?
• If this is an older paper, how has our perception of the topic and ideas changed in the intervening years? Does it raise conjectures that have since been answered one way or the other?
• What's next for this topic? What problems in the paper remain open today? What new mathematical questions does it suggest to you? What practical software tools might you build based on the ideas in the paper, or as research tools to study the topic?

Project

The course will culminate with a final project in which students will explore a topic related to tilings and computation, from either a theoretical or a practical perspective. The project can be completed alone, or in groups of two; marking will be the same either way.

Here's a tentative schedule for the term. We'll fill up this schedule as students claim papers and dates on which to present them. We may make other adjustments during the term as needed.

Policies

Generative AI

Generative artificial intelligence (GenAI) trained using large language models (LLM) or other methods to produce text, images, music, or code, like Chat GPT, DALL-E, or GitHub CoPilot, may be used under specific conditions in this course with proper documentation, citation, and acknowledgement.  Permitted uses of and expectations for using GenAI will discussed in class and outlined on assignment instructions.

That's the university's boilerplate text. Let me expand on it. Basically, I'm opposed to using Generative AI. I don't trust it to work reliably. When it's wrong, it's often wrong in subtle ways that are easy to miss, precisely because it's tuned for plausibility over correctness. More fundamentally, even if it worked flawlessly, you shouldn't use it. Generative AI certainly does nothing to make you smarter, and there's some evidence that it may even make you dumber (by stunting your critical thinking skills). If you weren't interested in becoming smarter, then why did you come to grad school?

The one place where I can offer some leeway is in using Generative AI to improve English writing. If you aren't a confident writer, then it's OK to treat a system like ChatGPT as a fancy grammar checker: you can feed in your draft text and have it spit out a polished version. It is your responsibility to look over the generated text carefully to make sure its meaning is preserved. You are required to disclose any AI tools that you used to help with writing and must, upon request, provide a transcript of your interaction with the tool.

Mental Health