Matthew L. Wright
Associate Professor, St. Olaf College

# Computational Geometry

## Math 282 ⋅ Spring 2019

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

Friday
February 8
Introduction
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.
Monday
February 11
Polygons: triangulations
Do the following before next class:
• Begin Homework 1.
• Read §1.2 Basic Combinatorics in the textbook.
Wednesday
February 13
Polygons: triangulations and combinatorics
Do the following before next class:
• Finish Homework 1.
• Read §1.3 The Art Gallery Theorem in the textbook.
Friday
February 15
Polygons: art gallery theorems
Homework 1
due today
Do the following before next class:
• Take a look at Homework 2.
• Read §1.4 Scissors Congruence in 2D in the textbook.
Monday
February 18
Polygons: scissors congruence
Do the following before next class:
Wednesday
February 20
Polygons and Polyhedra: scissors congruence
Do the following before next class:
• Finish Homework 2.
• Read §2.1 Convexity in the textbook.
Friday
February 22
Convexity and Convex Hulls
Homework 2
due today
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.
Monday
February 25
Convex Hulls: The Incremental Algorithm
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.
Wednesday
February 27
Convex Hulls: The Incremental Algorithm
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.
Friday
March 1
Homework 3
due today
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.
Monday
March 4
Convex Hulls: Gift Wrapping and Graham Scan
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.
Wednesday
March 6
Convex Hulls: Divide and Conquer
Do the following before next class:
• Finish Quiz 1.
• Read §3.1 Basic Constructions in the textbook.
Friday
March 8
Finish convex hulls; begin triangulation of point sets
Quiz 1
due today
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.
Monday
March 11
Triangulations
Do the following before next class:
• Work on Homework 5, due Friday.
• Read §3.2 The Flip Graph in the textbook.
Wednesday
March 13
Triangulations
Do the following before next class:
Friday
March 15
Delaunay Triangulations
Homework 5
due today
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.
Monday
March 18
Delaunay Triangulations
Do the following before next class:
Wednesday
March 20
Voronoi Diagrams
Do the following before next class:
• Finish Homework 6.
• Read §4.3 Duality and the Delaunay Triangulation in the textbook.
Friday
March 22
Voronoi Diagrams and Delaunay Triangulations
Homework 6
due today
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.
Monday
April 1
Algorithms for Voronoi Diagrams
Do the following before next class:
• Work on Quiz 2.
• Read §4.4 Convex Hull Revisited in the textbook.
Wednesday
April 3
Algorithms for Voronoi diagrams; revisit convex hulls
Do the following before next class:
Friday
April 5
The Medial Axis
(Prof. Wright at a conference. Sorry, no office hours today!)
Quiz 2
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
Voronoi Diagrams, Delaunay Triangulations, and Convex Hull
The Medial Axis and Straight Skeleton
Do the following before next class:
• Work on Homework 8.
• Read §5.2 Straight Skeleton in the textbook.
Wednesday
April 10
Minkowski Sums
Do the following before next class:
Friday
April 12
Minkowski Sums
Homework 8
due today
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.
Monday
April 15
Minkowski Sums and Curve Shortening
Do the following before next class:
• Work on Homework 9.
• Read §5.5 Curve Shortening in the textbook.
Wednesday
April 17
Curve Reconstruction
Do the following before next class:
• Finish Homework 9.
• Read §5.7 Curve Reconstruction in the textbook.
Friday
April 19
Platonic Solids and Semi-regular Polyhedra
Homework 9
due today
Do the following before next class:
• Read §6.1 Platonic Solids in the textbook.
• Take a look at Homework 10.
Monday
April 22
Euler's Polyhedral Formula
Do the following before next class:
• Work on Homework 10.
• Read §6.2 Euler's Polyhedral Formula.
Wednesday
April 24
Curvature and the Gauss-Bonnet Theorem
Do the following before next class:
• Finish Homework 10.
• Read §6.3 The Gauss-Bonnet Theorem.
Friday
April 26
Shortest paths on polyhedra
Homework 10
due today
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.
Monday
April 29
Shortest paths on polyhedra
Do the following before next class:
• Re-read §6.5 Shortest Paths in the textbook.
• Work on Quiz 3.
Wednesday
May 1
Geodesics
Do the following before next class:
• Finish Quiz 3.
• Read §6.6 Geodesics in the textbook.
Friday
May 3
Configuration Spaces: Motion Planning
Quiz 3
due today
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.
Monday
May 6
Configuration Spaces: Motion Planning and Polygonal Chains
Do the following before next class:
Wednesday
May 8
Configuration Spaces: Polygonal Chains
Do the following before next class:
Friday
May 10
Configuration Spaces: Polygonal Systems
Homework 12
due today
Do the following before next class:
• Read §7.4 Polygon Spaces in the textbook.
• Work on your final project.
Monday
May 13
Final projects
Do the following before next class:
Wednesday
May 15
Final projects
Do the following before the final exam period: