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