Math 4990

Fall 2015

Discrete Geometry

Basic Information

• Instructor: Jed Yang,
• Lectures: Tuesdays 16:00–18:00 in Vincent Hall 364
• Course website: http://math.umn.edu/~jedyang/4990.15f/

Course Description

Discrete 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 References

We 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.

Grading

There 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

1. understand your solutions,
2. write your solutions in your own words without copying, and
3. indicate the names of your collaborators.

If you copy work (or collaborate without indicating so), UMN academic dishonesty policies shall be applied.

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.

Calendar

To be updated throughout the term; tentative and subject to change.

Date		Topics	Homework
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

Supplemental Material

• 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

Announcements

• 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.

---