Math 4990

Fall 2014

Discrete Geometry

Basic Information

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

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. A small percentage will be based on style points.

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	02	Triangulations [DO §1.1]	Problem Set 1 and solutions
	09	Catalan numbers (handout), art galleries [DO §§1.2–1.3; AZ §31]	Problem Set 2 and solutions
	16	Scissors congruence [DO §§1.4–1.5; AZ §6, §8; P §15] (notes)	Problem Set 3 and solutions
	23	Convex hulls, Helly theorem [DO §2.1; P §1]	Problem Set 4 and solutions
	30	Triangulations [DO §3.1]	Problem Set 5 and solutions
October	07	Flip graph and Voronoi diagrams [DO §3.2, §4.1]	Problem Set 6 and solutions
	14	Delaunay triangulations [DO §§4.3–4.4, 3.4; P §14]	Problem Set 7 and solutions
	21	Domino tilings	Problem Set 8 and solutions
	28	Platonic solids, Euler's formula revisited, Gauss–Bonnet theorem [DO §§6.1–6.3]	Problem Set 9 and solutions
November	04	Fair division: equipartitions [P §4]	Problem Set 10 and solutions
	11	Fair division: Sperner's Lemma [Su]	Problem Set 11 and solutions
	18	Cauchy rigidity [DO §6.4]	Problem Set 12 and solutions
	25	Thanksgiving, no class
December	02	Polygonal chains [DO §§7.2–7.3] (class cancelled)	Problem Set 13 and solutions
	09	Universality of linkages [P §13]
	16	Computational complexity

Supplemental Material

• Sep 09: Information on Catalan numbers collated by Igor Pak
• Sep 16: Triangle dissection paradox
• Oct 07: Proper drawings of planar graphs
• Oct 07: Voronoi diagram of world airports
• Oct 21: The On-Line Encyclopedia of Integer Sequences
• Nov 11: Envy-free rent division calculator
• Nov 18: Steffen's flexible polyhedron pattern

---