Math 4990

Fall 2015

Discrete Geometry

Basic Information

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


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.


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

September 08Triangulations [DO §1.1] Problem Set 1 and solutions
15Catalan numbers (handout) [DO §1.2] Problem Set 2 and solutions
22Art galleries, scissors congruence [DO §§1.3–1.4; AZ §31; P §15] Problem Set 3 and solutions
29Dehn invariants (notes) [DO §1.5; AZ §6, §8] Problem Set 4 and solutions
October 06Convex hulls, Helly theorem [DO §2.1; P §1] Problem Set 5 and solutions
13Triangulations [DO §3.1] Problem Set 6 and solutions
20Flip graph and Voronoi diagrams [DO §3.2, §4.1] Problem Set 7 and solutions
27Delaunay triangulations [DO §§4.3–4.4, 3.4; P §14] Problem Set 8 and solutions
November 03Domino tilings Problem Set 9 and solutions
10Platonic solids, Euler's formula revisited, Gauss–Bonnet theorem [DO §§6.1–6.3] Problem Set 10 and solutions
17Fair division [P §4] Problem Set 11 and solutions
24Thanksgiving, no class
December 01Envy-free division [Su] Problem Set 12
08Cauchy rigidity [DO §6.4] Problem Set 13
15Eat pizzas with robots

Supplemental Material


Last Modified 2015.12.09.
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.