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