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)