- Instructor: Jed Yang,
- Lectures: Tuesdays 16:00–18:00 in Vincent Hall 364
- Course website: http://math.umn.edu/~jedyang/4990.15f/
Course DescriptionDiscrete geometry is the study of combinatorial properties of discrete geometric objects such as points, lines, spheres, and polyhedra. We will survey a variety of topics such as triangulations, incidence structures, packings and tilings, convex bodies, and structural rigidity. For example, given two polygons with the same area, we can dissect one and rearrange the resulting smaller polygonal pieces to form the second polygon. However, given two polyhedra with the same volume, it may not be possible to dissect one to form the second. We will discuss this fascinating phenomenon, and also classical problems like dividing objects fairly, guarding art galleries with the minimum number of security cameras, and finding shortest paths on polyhedral surfaces.
An auxiliary goal of this course is for students to master the arts of mathematical communication, notably proof writing.
Textbook and ReferencesWe plan to cover various sections of [DO] and possibly supplement with other sources such as [AZ] and [P].
- [AZ] Martin Aigner and Günter M. Ziegler, Proofs from THE BOOK, Springer; 3rd ed., 2003.
- [DO] Satyan Devadoss and Joseph O'Rourke, Discrete and Computational Geometry, Princeton University Press, 2011. [Errata]
- [P] Igor Pak, Lectures on Discrete and Polyhedral Geometry, manuscript.
- [Su] Fancis Su, Rental harmony: Sperner's lemma in fair division, Amer. Math. Monthly 106 (1999), 930–942.
GradingThere will be no examinations provided that the homework scores are reasonably high (e.g., no one below a B average).
Your grades will be determined by a weighted arithmetic mean of the following two categories:
Homework (90%)Weekly problem sets will be posted on the course website after each lecture and due at the beginning of the next lecture. Late homework will not be accepted for credit. The worst homework will be dropped.
Collaboration is encouraged, as long as you
- understand your solutions,
- write your solutions in your own words without copying, and
- indicate the names of your collaborators.
Class attendance and participation (10%)If you will be absent for any reason, please let the instructor know in advance, if possible. Please refrain from using electronic devices (such as cell phones, laptops, or iPods) in class.
|September||08||Triangulations [DO §1.1]||Problem Set 1 and solutions|
|15||Catalan numbers (handout) [DO §1.2]||Problem Set 2 and solutions|
|22||Art galleries, scissors congruence [DO §§1.3–1.4; AZ §31; P §15]||Problem Set 3 and solutions|
|29||Dehn invariants (notes) [DO §1.5; AZ §6, §8]||Problem Set 4 and solutions|
|October||06||Convex hulls, Helly theorem [DO §2.1; P §1]||Problem Set 5 and solutions|
|13||Triangulations [DO §3.1]||Problem Set 6 and solutions|
|20||Flip graph and Voronoi diagrams [DO §3.2, §4.1]||Problem Set 7 and solutions|
|27||Delaunay triangulations [DO §§4.3–4.4, 3.4; P §14]||Problem Set 8 and solutions|
|November||03||Domino tilings||Problem Set 9 and solutions|
|10||Platonic solids, Euler's formula revisited, Gauss–Bonnet theorem [DO §§6.1–6.3]||Problem Set 10 and solutions|
|17||Fair division [P §4]||Problem Set 11 and solutions|
|24||Thanksgiving, no class|
|December||01||Envy-free division [Su]||Problem Set 12|
|08||Cauchy rigidity [DO §6.4]||Problem Set 13|
|15||Eat pizzas with robots|
- Sep 15: Information on Catalan numbers curated by Igor Pak
- Sep 22: Triangle dissection paradox
- Oct 20: Proper drawings of planar graphs
- Oct 20: Voronoi diagram of world airports
- Nov 03: The On-Line Encyclopedia of Integer Sequences
- Dec 01: Diana Davis on average pace in running [PDF]
- Dec 01: Envy-free rent division calculator
- Dec 08: Steffen's flexible polyhedron pattern
- Sep 14: Classroom changed to VinH 364.
- Sep 16: Moodle forum for homework discussion is functional.
- Sep 23: Homework 1 grades entered into Moodle; please check for accuracy.
- Dec 08: Homework 1–11 grades entered into Moodle; please check for accuracy.
The views and opinions expressed in this page are strictly those of the page author.
The contents of this page have not been reviewed or approved by the University of Minnesota.
Sat and forever am at work here.