This is a past course that has already concluded. If you are looking for a current course, please click here.
Welcome to Computational Geometry! For course info and policies, please see the syllabus. For grades, log into Moodle. If you need help, contact Prof. Wright.
Office hours: Mon. 9–10, Tues. 10–11, Wed. 10:30–11:30, Thurs. 1–2, Fri. 9–10 (see Moodle for the Zoom link)
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
February 16
Introduction; Art gallery problem
Do the following before the next class:
- Complete the syllabus quiz.
- In the textbook, read sections 1.1 (diagonals and triangulations) and 1.2 (basic combinatorics) and complete the reading questions on Moodle.
- Take a look at Homework 1, which is due next Tuesday.
Thursday
February 18
February 18
Triangulations
Do the following before the next class:
- Finish Homework 1 (due 5pm Tuesday). Upload your solutions to Moodle.
- In the textbook, read section 1.3 (art gallery theorem) and and complete the reading questions on Moodle.
Tuesday
February 23
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
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
March 2
Convex hulls
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
March 4
Convex hulls: incremental algorithm
Bonus video: Steven Strogatz — The science of sync
Do the following before the next class:
- In the textbook, read section 2.4 (gift wrapping and Graham scan algorithms) and complete the reading questions on Moodle.
- Finish Homework 3. Upload your solutions to Moodle.
Tuesday
March 9
March 9
Convex hulls: gift wrapping and Graham scan
Do the following before the next class:
- In the textbook, read sections 2.5 – 2.7 (i.e., the rest of chapter 2). Complete the reading questions on Moodle.
- Take a look at Homework 4, due next Tuesday.
Thursday
March 11
March 11
Convex hulls: Graham scan and divide-and-conquer
Do the following before the next class:
- Finish Homework 4. Upload your solutions to Moodle.
- Complete Quiz 1 on Moodle.
Tuesday
March 16
March 16
Triangulations
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
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
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
March 25
Voronoi diagrams
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
March 30
Voronoi diagrams
Do the following before the next class:
- In the textbook, read the rest of Chapter 4.
- View the Fortune's algorithm animation and explore the Fortune's algorithm demonstration.
- Please complete the Mid-Semester Survey.
- Take a look at Homework 7, due next Tuesday.
Thursday
April 1
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
April 6
Medial axis and straight skeleton
Enjoy a rest day!
Thursday
April 8
April 8
Minkowski sums
Do the following before the next class:
- Take a look at Homework 8, due next Thursday.
- In the textbook, read section 5.2 (straight skeleton) and section 5.3 (Minkowski sums). Answer the reading questions on Moodle.
Tuesday
April 13
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
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.
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
April 22
Euler Characteristic and Curvature
Tuesday
April 27
April 27
Rest Day — no class
Do the following before the next class:
- Begin Homework 10 (due Tuesday, May 4).
- Read section 6.3 (Gauss-Bonnet theorem).
- Review the Final Project Information and think about what topic you will choose.
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
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.
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.
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
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
May 18
Final projects
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
May 25
9–11am: Final presentations (online)