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: 2:30 – 3:30pm daily in RMS 405

Top

Today

Bottom

Tuesday

January 3

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

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.*

Do the following before the next class:

- In the textbook, read Sections 1.4 and 1.5 (scissors congruence in 2D and 3D). For more examples of geometric dissections, see Gavin Theobald's site. This is the interactive demo by Smirnova and Epstein.
- Begin work on Homework 2, which is due Monday.
- Review the Quiz 1 Information and study for the quiz.

Friday

January 6

January 6

Convex hulls

**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

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

Homework 2

due

due

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

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.

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.

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.

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

January 17

Delaunay triangulations and special triangulations

Do the following before the next class:

- In the textbook, read Sections 3.4 (Delaunay triangulations) and 3.5 (special triangulations).
- Read the Final Project Information. Think about what topics interest you and who you would like to work with for the final project.
- Finish Homework 5 and upload your solutions to the Homework 5 assignment on Moodle.

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

January 19

Voronoi and Delaunay

**Quiz 3**

Do the following before the next class:

- In the textbook, read Sections 4.3 (duality and the Delaunay triangulation) and 4.4 (convex hull revisited). View the Fortune's Algorithm animation and interactive demo.
- Finish Homework 6 and upload your solutions to the Homework 6 assignment on Moodle.

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

January 23

Curve reconstruction; final projects

Do the following before the next class:

- In the textbook, read Section 5.7 (curve reconstruction).
- Finish Homework 7, and upload your solution to the Homework 7 assignment on Moodle.
- Work on your final project.

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.

Do the following before the next class:

- In the textbook, read Section 6.2 (Euler's polyhedral formula).
- Finish Homework 8 and upload your solution to the Homework 8 assignment on Moodle.
- Work on your final project.

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

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

January 28

**Final Presentations: 10:30am —12:30pm in RNS 310**