Matthew L. Wright
Associate Professor, St. Olaf College

Computational Geometry

Math 282 ⋅ Spring 2021

    This is a past course that has already concluded. If you are looking for a current course, please click here.

Top
Today
Bottom
Do the following before the first class:
  • Complete the Introductory Survey.
  • 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.
Tuesday
February 16
Introduction; Art gallery problem
Do the following before the next class:
Thursday
February 18
Triangulations
Do the following before the next class:
Tuesday
February 23
Art gallery theorems — meet in RNS 290
Do the following before the next class:
  • In the textbook, read section 1.4 (scissors congruence) and complete the reading questions on Moodle.
  • If possible, bring a pair of scissors to class on Thursday.
  • Take a look at Homework 2, due next Tuesday.
Thursday
February 25
Scissors congruence
Do the following before the next class:
  • In the textbook, read section 2.1 (convexity). There are no reading questions for this section, but the important thing is to understand what is the convex hull of a set of points.
  • Finish Homework 2. Upload your solutions to Moodle.
Tuesday
March 2
Do the following before the next class:
  • In the textbook, read sections 2.2 (the incremental algorithm) and 2.3 (analysis of algorithms), and complete the reading questions on Moodle.
  • Take a look at Homework 3, due next Tuesday.

Extra credit opportunity: Attend either of Dr. Trachette Jackson's lectures on March 2 or 3 and answer these two questions on Moodle to earn two extra-credit points.

Thursday
March 4
Convex hulls: incremental algorithm

Bonus video: Steven Strogatz — The science of sync

Do the following before the next class:
Tuesday
March 9
Convex hulls: gift wrapping and Graham scan
Do the following before the next class:
Thursday
March 11
Convex hulls: Graham scan and divide-and-conquer
Do the following before the next class:
Tuesday
March 16
Do the following before the next class:
  • In the textbook, read section 3.1 (triangulations — basic constructions). There are no reading questions.
  • Take a look at Homework 5, due next Tuesday.
Thursday
March 18
Triangulations
Do the following before the next class:
  • In the textbook, read section 3.2 (the flip graph) and section 3.4 (Delaunay triangulations) up to the horizontal line on page 83. Complete the reading questions on Moodle.
  • Finish Homework 5. Upload your solutions to Moodle.
Tuesday
March 23
Delaunay triangulations
Do the following before the next class:
  • In the textbook, finish reading section 3.4 (Delaunay triangulations) and read section 4.1 (Voronoi geometry). Answer the reading questions on Moodle.
  • Take a look at Homework 6, due next Tuesday.
Thursday
March 25
Do the following before the next class:
  • In the textbook, read section 4.2 (algorithms) and 4.3 (duality), at least up to the horizontal line on page 109. There are no reading questions for Tuesday.
  • Finish Homework 6. Upload your solutions to Moodle.
Tuesday
March 30
Do the following before the next class:
Thursday
April 1
Finish Voronoi, begin medial axis
Do the following before the next class:
  • Finish Homework 7. Upload your solutions to Moodle.
  • Complete Quiz 2 on Moodle.
  • In the textbook, read section 5.1 (medial axis). There are no reading questions.
Tuesday
April 6
Medial axis and straight skeleton
Enjoy a rest day!
Thursday
April 8
Minkowski sums
Do the following before the next class:
Tuesday
April 13
Minkowski sums and curve shortening
Do the following before the next class:
  • Finish at Homework 8. Upload your solutions to Moodle.
  • Read section 5.5 (curve shortening). Optionally read section 5.6 (connections between curve shortening, the heat equation, and the PoincarĂ© conjecture).
Thursday
April 15
CRUST algorithm
Do the following before the next class:
  • Read section 5.7 (curve reconstruction) and section 6.1 (Platonic solids).
  • Read the Final Project Info and think about possible topics for your final project.
  • Take a look at Homework 9, due next Thursday.
Tuesday
April 20
Polyhedra
Do the following before the next class:
  • Finish Homework 9. Upload your solutions to Moodle.
  • Read section 6.2 (Euler's polyhedral formula).
Thursday
April 22
Euler Characteristic and Curvature
Tuesday
April 27
Rest Day — no class
Do the following before the next class:
Thursday
April 29
Shortest paths on polyhedra
Do the following before the next class:
  • Finish Homework 10. Upload your solutions to Moodle.
  • Read section 6.5 (shortest paths) in the textbook.
Tuesday
May 4
Geodesics
Do the following before the next class:
  • Take a look at Homework 11 (due Thursday, May 13).
  • Decide on a topic for the final project and look for resources on your topic.
  • Read section 6.6 (geodesics) in the textbook.
Thursday
May 6
Configuration spaces
Do the following before the next class:
  • Complete Quiz 3 on Moodle before class on Tuesday.
  • Work on Homework 11 (due Thursday, May 13).
  • Read section 7.1 (motion planning) in the textbook.
  • Identify one or more goals for your final project (review the final project info) and continue gathering sources of information on your topic.
Tuesday
May 11
Configuration spaces
Do the following before the next class:
  • Finish Homework 11 (due Thursday, May 13).
  • Work on your final project.
  • Read sections 7.2 (polygonal chains) and 7.3 (rulers and locked chains) in the textbook.
Thursday
May 13
Configuration spaces (HW 11 due)
Do the following before the next class:
  • Work on your final project.
  • Read sections 7.4 (polygon spaces) and 7.5 (particle collisions) in the textbook.
Tuesday
May 18
Do the following before the final exam period:
  • Finish your Final Project and submit your files to Moodle.
  • Prepare to give a brief presentation (not more than 5 minutes per person) about your project at the final exam period on May 25.
  • Please complete the Course Evaluation.
Tuesday
May 25
9–11am: Final presentations (online)