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.
Prof. Wright's office hours in RMS 405: Mon. 10:30–11:30, Tues. 1:30–2:30, Wed. 8:00–9:00, Thurs 10:15–11:00, Fri. 2:00–3:00, whenever the door is open, or by appointment
Jump to today
Jump to top
Do the following before next class:
- Complete the syllabus quiz.
- Read §1.1 Diagonals and Triangulations in the textbook.
- Take a look at Homework 1, which is due next Friday.
Do the following before next class:
- Begin Homework 1.
- Read §1.2 Basic Combinatorics in the textbook.
Do the following before next class:
- Finish Homework 1.
- Read §1.3 The Art Gallery Theorem in the textbook.
Do the following before next class:
- Take a look at Homework 2.
- Read §1.4 Scissors Congruence in 2D in the textbook.
Do the following before next class:
- Explore the Scissors congruence interactive demonstration.
- Begin Homework 2.
- Read §1.5 Scissors Congruence in 3D in the textbook.
Do the following before next class:
- Finish Homework 2.
- Read §2.1 Convexity in the textbook.
Do the following before next class:
- Take a look at Homework 3.
- Think about: How would you program a computer to find the convex hull of a set of points in the plane?
- Read §2.2 The Incremental Algorithm in the textbook.
Do the following before next class:
- Begin Homework 3.
- Read §2.3 Analysis of Algorithms and §2.4 Gift Wrapping and Graham Scan in the textbook.
- If possible, bring a computer with Mathematica to class on Wednesday.
Do the following before next class:
- Finish Homework 3.
- Read §2.3 Analysis of Algorithms and §2.4 Gift Wrapping and Graham Scan in the textbook.
- If possible, bring a computer with Mathematica to class on Friday.
Do the following before next class:
- Try to complete the missing line of code in the gift wrapping Mathematica notebook. Bring your best attempt at this to class on Monday!
- Read §2.5 Lower Bound in the textbook.
- Take a look at Quiz 1, due next Friday.
Do the following before next class:
- Extra credit opportunity: attend the colloquium by Shilad Sen (March 4, 3:30pm in RNS 310) and answer these two questions on Moodle. (Responses due Wednesday.)
- Begin Quiz 1, if you haven't done so already.
- Read §2.6 Divide-and-Conquer and §2.7 Convex Hull in 3D in the textbook.
Do the following before next class:
- Finish Quiz 1.
- Read §3.1 Basic Constructions in the textbook.
Do the following before next class:
- Take a look at Homework 5.
- Think about: What algorithm would you use to find a triangulation of a set of points? How could you find all triangulations?
- Re-read §3.1 Basic Constructions in the textbook.
Do the following before next class:
- Work on Homework 5, due Friday.
- Read §3.2 The Flip Graph in the textbook.
Do the following before next class:
- Finish Homework 5.
- Check out these twenty proofs of Euler's formula.
- Read §3.4 Delaunay Triangulations in the textbook.
Do the following before next class:
- Take a look at Homework 6.
- Re-read §3.4 Delaunay Triangulations in the textbook.
- Read §3.5 Special Triangulations in the textbook.
Do the following before next class:
- Explore the Thales' Theorem demonstration.
- Begin Homework 6.
- Read §4.1 Voronoi Geometry in the textbook.
Do the following before next class:
- Finish Homework 6.
- Read §4.3 Duality and the Delaunay Triangulation in the textbook.
Have a great spring break! No class March 25 – 29.
Do the following before next class:
- Read §4.2 Algorithms to Construct the Diagram in the textbook.
- Take a look at Quiz 2, which is due on Friday, April 5.
- Think about what topic(s) interest you for the final project. See the final project information.
Do the following before next class:
- Work on Quiz 2.
- Read §4.4 Convex Hull Revisited in the textbook.
Do the following before next class:
- Finish Quiz 2. If you have questions, ask Prof. Wright on Thursday.
- View the Fortune's algorithm animation and explore the Fortune's algorithm demonstration.
Friday
April 5
April 5
The Medial Axis
(Prof. Wright at a conference. Sorry, no office hours today!)
(Prof. Wright at a conference. Sorry, no office hours today!)
Quiz 2
due today
due today
Do the following before next class:
- Read §5.1 Medial Axis in the textbook.
- Take a look at Homework 8.
Monday
April 8
April 8
Voronoi Diagrams, Delaunay Triangulations, and Convex Hull
The Medial Axis and Straight Skeleton
The Medial Axis and Straight Skeleton
Do the following before next class:
- Work on Homework 8.
- Read §5.2 Straight Skeleton in the textbook.
Do the following before next class:
- Finish Homework 8.
- Read §5.3 Minkowski Sums in the textbook.
- Think about what topic(s) interest you for the final project. See the final project information.
Do the following before next class:
- Re-read §5.3 Minkowski Sums in the textbook. Optionally, read §5.4 Convolution of Curves.
- Think about what topic(s) interest you for the final project. See the final project information.
- Look at Homework 9, to be posted soon.
Do the following before next class:
- Work on Homework 9.
- Read §5.5 Curve Shortening in the textbook.
Do the following before next class:
- Finish Homework 9.
- Read §5.7 Curve Reconstruction in the textbook.
Do the following before next class:
- Read §6.1 Platonic Solids in the textbook.
- Take a look at Homework 10.
Do the following before next class:
- Work on Homework 10.
- Read §6.2 Euler's Polyhedral Formula.
Do the following before next class:
- Finish Homework 10.
- Read §6.3 The Gauss-Bonnet Theorem.
Do the following before next class:
- Read §6.5 Shortest Paths in the textbook.
- Take a look at Quiz 3, which is due Friday, May 3.
Do the following before next class:
- Re-read §6.5 Shortest Paths in the textbook.
- Work on Quiz 3.
Do the following before next class:
- Finish Quiz 3.
- Read §6.6 Geodesics in the textbook.
Do the following before next class:
- Decide on a topic (and optionally a group) for the final project.
- Take a look at Homework 12.
- Read §7.1 Motion Planning in the textbook.
Do the following before next class:
- Read §7.2 Polygonal Chains in the textbook.
- Work on your final project.
- Begin Homework 12.
Do the following before next class:
- Finish Homework 12.
- Read §7.3 Rulers and Locked Chains in the textbook.
- Work on your final project.
Do the following before next class:
- Read §7.4 Polygon Spaces in the textbook.
- Work on your final project.
Monday
May 13
May 13
Final projects
Do the following before next class:
- Work on your final project.
- If you are new to LaTeX, see this quick guide to LaTeX for help typesetting your paper.
- Complete the Final Project Update on Moodle.
Wednesday
May 15
May 15
Final projects
Do the following before the final exam period:
- Finish your final project.
- Save your paper in PDF format.
- Prepare to give a brief presentation of your project at the final exam period.
- Upload your work to the Final Project Submission on Moodle.
Monday
May 20
May 20
9–11am: Final exam/presentations
