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
Friday
January 3
January 3
Introduction; Triangulations
Do the following before the next class:
- Complete the Introductory Survey.
- Read the syllabus and complete the Syllabus Quiz on Moodle.
- 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 Tuesday.
Monday
January 6
January 6
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 Thursday.
- Review the Quiz 1 Information and study for the quiz.
Wednesday
January 8
January 8
Convex hulls — incremental algorithm
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 tomorrow. Upload your solutions to Homework 2 on Moodle.
Do the following before the next class:
- In the textbook, read Sections 2.3 (analysis of algorithms) and 2.4 (gift wrapping and graham scan algorithms).
- To see why sorting a list of \(n\) items can be accomplished in \(O(n\log(n))\) time, watch this video about the mergesort algorithm.
- Also read the appendix on computational complexity, pages 245–247 in the text.
- Begin work on Homework 3, which is due Monday.
Friday
January 10
January 10
Do the following before the next class:
- In the textbook, read Sections 2.5 (lower bound on convex hull algorithm complexity), 2.6 (divide-and-conquer algorithm), and 2.7 (convex hull in 3D).
- Finish on Homework 3. Upload your solutions to Homework 3 on Moodle.
Monday
January 13
January 13
10:40am–noon: class: triangulations
1:00–2:20pm: no class
3:00–4:00pm: attend CS candidate presentation in RNS 410
1:00–2:20pm: no class
3:00–4:00pm: attend CS candidate presentation in RNS 410
Homework 3
due
due
Do the following before the next class:
- In the textbook, read Section 3.1 (triangulations of point sets; basic constructions).
- Review the Quiz 2 Information and study for the quiz.
- Begin work on Homework 4, which is due Wednesday.
Do the following before the next class:
- In the textbook, read Section 3.2 (the flip graph).
- 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.4 (Delaunay triangulations) and 3.5 (special triangulations).
- Optionally, read Section 3.3 (associahedron) in the textbook.
- Begin work on Homework 5, which is due Friday.
Thursday
January 16
January 16
Voronoi diagrams
Do the following before the next class:
- In the textbook, read Sections 4.1 (Voronoi geometry) and 4.2 (algorithms).
- 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.
Martin Luther King, Jr. Day — no class on Monday, January 20
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.
- Re-read the Final Project Information. Identify 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.
Tuesday
January 21
January 21
Medial axis and straight skeleton
Quiz 3
Do the following before the next class:
- In the textbook, read Sections 5.1 (meidal axis) and 5.2 (straight skeleton).
- 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.3 (Minkowski sums) and 5.7 (curve reconstruction).
- 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 Friday.
Thursday
January 23
January 23
Polyhedra; final projects
Do the following before the next class:
- Reading to be announced.
- 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:
Monday
January 27
January 27
Polyhedra and curvature; final projects
Quiz 4
Do the following before the next class:
Tuesday
January 28
January 28
Unfolding polyhedra; final projects
Homework 8
due
due
Do the following before the next class:
Wednesday
January 29
January 29
Shortest paths on polyhedra; final projects
Do the following before the next class:
Thursday
January 30
January 30
Final Presentations: 8:00am —10:00am
