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