Matthew L. Wright
Associate Professor, St. Olaf College

# Computational Geometry

## Math 282 ⋅ January 2023

Top
Today
Bottom
Tuesday
January 3
Introduction; Triangulations
Do the following before the next class:
• Complete the Introductory Survey, if you haven't done so already.
• If possible, install Mathematica on your computer. If you've already installed Mathematica, open it up and check that your license key is still active. You might be prompted to upgrade to the most recent version. For assistance, see this IT Help Desk page.
• In the textbook, read Sections 1.1 (diagonals and triangulations) and 1.2 (basic combinatorics) .
• Begin work on Homework 1, which is due Thursday.
Wednesday
January 4
Art gallery problems
Do the following before the next class:
• In the textbook, read Section 1.3 (the art gallery theorem) .
• Finish Homework 1, which is due tomorrow. Upload your solutions to Homework 1 on Moodle.
• If possible, bring a pair of scissors to class tomorrow.
Thursday
January 5
Scissors congruence
Do the following before the next class:
Friday
January 6
Quiz 1
on Sections 1.1–1.3
Do the following before the next class:
• In the textbook, read Sections 2.1 (convexity) and 2.2 (incremental algorithm).
• Finish Homework 2, which is due Monday.
Monday
January 9
10:40am–noon: no class
1:00–2:20pm: class: convex hull gift wrapping algorithm
3:30–4:30pm: attend CS candidate presentation in RNS 310
Do the following before the next class:
• In the textbook, read Section 2.3 (analysis of algorithms) and 2.4 up to the blue box about the gift wrapping algorithm.
• Also read the appendix on computational complexity, pages 245–247 in the text.
• Begin work on Homework 3, which is due Wednesday.
Tuesday
January 10
10:40am–noon: no class
12:30–1:00pm: lunch with CS candidate in RNS 310
1:00–2:20pm: class: convex hull Graham scan algorithm
3:30–4:30pm: attend CS candidate presentation in RNS 310
Do the following before the next class:
• In the textbook, finish reading section 2.4 (Graham scan algorithm). Also read section 2.5 (lower bound on the complexity of convex hull algorithms).
• Finish on Homework 3. Upload your solutions to Homework 3 on Moodle.
Wednesday
January 11
Convex hulls: divide-and-conquer
meet at 10:40am in RNS 203
Do the following before the next class:
• In the textbook, read Sections 2.6 (divide-and-conquer) and 2.7 (convex hulls in 3D).
• Review the Quiz 2 Information and study for the quiz.
• Begin work on Homework 4, which is due Friday.
Thursday
January 12
Triangulations
Quiz 2
Do the following before the next class:
• In the textbook, read Section 3.1 (basic constructions) and at least the first two pages of Section 3.2 (the flip graph, pages 66–67).
• Finish Homework 4 and upload your solutions to Homework 4 on Moodle.
Friday
January 13
Triangulations
Do the following before the next class:
• In the textbook, read Sections 3.2 (flip graph) and 3.3 (associahedron).
• Begin work on Homework 5, which is due next Wednesday.
Tuesday
January 17
Delaunay triangulations and special triangulations
Do the following before the next class:
Wednesday
January 18
Voronoi diagrams
Do the following before the next class:
• In the textbook, read Sections 4.1 (Voronoi geometry) and 4.2 (algorithms).
• Re-read the Final Project Information. Choose three possible topics that interest you for the final project and consider who you would like to work with. Complete the Project Planning Survey to indicate your topic ideas and group preferences.
• Review the Quiz 3 Information and study for the quiz.
• Begin work on Homework 6, which is due Friday.
Thursday
January 19
Voronoi and Delaunay
Quiz 3
Do the following before the next class:
Friday
January 20
Medial axis and straight skeleton
Do the following before the next class:
• In the textbook, read Sections 5.1 (medial axis) and 5.2 (straight skeleton).
• Find some resources (e.g., books, websites, papers) for your final project. Discuss with your group. Refine your topic if necessary.
• Begin work on Homework 7, which is due Tuesday.
Monday
January 23
Curve reconstruction; final projects
Do the following before the next class:
Tuesday
January 24
Polyhedra; final projects
Do the following before the next class:
• In the textbook, read Section 6.1 (polyhedra).
• Begin Homework 8.
• Review the Quiz 4 Information and study for the quiz.
• Work on your final project.
Wednesday
January 25
Euler's polyhedral formula; final projects
Quiz 4
Do the following before the next class:
Thursday
January 26
Polyhedra and curvature; final projects
Do the following before the next class:
• In the textbook, read Section 6.3 (Gauss-Bonnet theorem).
• Please complete the Course Evaluation.
• Work on your final project.
Friday
January 27
Unfolding polyhedra; final projects
Do the following before the next class:
• In the textbook, read Section 6.5 (shortest paths).
• Finish your final project. Upload your paper and code/output files to the Final Project Assignment on Moodle.
• Prepare to give a brief presentation (3–4 minutes per person) of your final project.
• Complete the Final Project: Self and Peer Evaluation. This is a short, required form regarding your own contributions and your group members' contributions to the project.
Saturday
January 28
Final Presentations: 10:30am —12:30pm in RNS 310