# CSE546: Computational Geometry (Fall 2017)

###### Calendar
This is a day-by-day list of events happening in the semester, including lectures, homework out/due dates, exam dates, and project due date.

###### Lectures
This is an approximate list of lectures and exams (see calendar above for timing). After each class, I will post locations of relevant materials in the textbook (the "Book") and/or Dave Mount's notes (the "Notes"). Links to cool demos and videos will also be provided whenever possible.
• Lecture 1: Introduction and convex hulls (Slides) and convex hulls (Notes: Lecture 1 and first part of Lecture 3; Book: Chapter 1)
• Lecture 2: Relation between convex hull and sorting Relation between convex hull and sorting (Notes: last part of Lecture 3 and beginning of Lecture 4)
• Lecture 3: Output sensitive complexity and Chan's convex hull algorithm (Notes: most of Lecture 4; additional reading)
• Lecture 4: Line segment intersection Line segment intersection (Notes: Lecture 5; Book: Chapter 2.1)
• Lecture 5: Planar subdivisions (Notes: beginning of Lecture 6 and all of Lecture 23; Book: Chapter 2.2 and 2.3)
• Lecture 6: Art Gallery Theorem (Notes: rest of Lecture 6; Book: Chapter 3.1)
• Lecture 7: Polygon triangulation (Notes: Lecture 7; Book: Chapter 3.2 and 3.3; slides on monotone polygon triangulation; The famous linear time algorithm)
• Lecture 8: Kirkpatrick's point location algorithm (Notes: Lecture 25; A cool demo)
• Lecture 9: Point location by trapezoidal decomposition (Notes: Lectures 14, 15; Book: Chapter 6.1, 6.2)
• Lecture 10: Voronoi diagrams (Notes: Lectures 16 first part; Book: Chapter 7.1; a demo)
• Lecture 11: Delaunay triangulations (Notes: Lectures 17 first part; Book: Chapter 9.1, 9.2)
• Lecture 12: Relation between Delaunay triangulations and convex hull (Notes: Lectures 28)
• EXAM 1 (Oct 10th) (practice problems and hints)
• Lecture 13: Fortune's algorithm for computing Voronoi diagrams (Notes: Lecture 16 second part; Book: Chapter 7.2; a demo)
• Lecture 14: Incremental construction of Delaunay triangulations (Notes: Lecture 18; Book: Chapters 9.3, 9.4)
• Lecture 15:Alpha hulls and variations of Voronoi Diagrams (Slides)
• Lecture 16: Point/line duality (Notes: Lecture 8; Book: Chapter 8.2; a demo)
• Lecture 17: Ham Sandwitch Theorem and line arrangement (Notes: Lecture 30)
• Lecture 18: Zone Theorem and computing line arrangement (Notes: Lecture 19; Book: Chapter 8.3)
• Lecture 19: Applications of line arrangement (Notes: Lecture 20; Book: Chapter 8.1, 8.4)
• Lecture 20: 1D range queries and binary trees (Notes: first part of Lecture 11; Book: Chapter 5.1)
• Lecture 21: 2D range queries, Kd trees and Orthogonal range trees (Notes: latter part of Lecture 11, Lecture 12; Book: Chapter 5.2, 5.3; slides)
• Lecture 22: Interval trees (Notes: Lecture 24; Book: Chapter 10.1; slides )
• Lecture 23: Shortest paths and visibility graphs (Notes: Lecture 21; Book: Chapter 15)
• Lecture 24: Motion planning (Notes: Lecture 22; Book: Chapter 13; A cool visualization of configuration space for rotational robots)
• EXAM 2 (Dec 5th) (practice problems with hints)

###### Homework
You have 2 weeks for completing each homework, which should be turned in before class on the noted dates (I will collect the homework during class on the due date). Each homework should be turned in with this cover sheet. Read the academic integrity policy before you start.

Note 1: I strongly encourage you to typeset your answers (in Word, or Latex, or else). If you choose to turn in hand-written answers, write clearly enough for TAs and graders to read.

Note 2: For *all* problems you must give (unless specified otherwise in the homework handout):
1. a pseudocode description of the algorithm
2. an analysis of the runtime
3. an argument that the algorithm gives the correct output on all possible inputs.
###### Final project
Final project specifications. It is due by midnight December 17th.

###### Course resources
This class builds on a large number of results, algorithms and data structures. I expect you've seen most of these in your discrete math, or data structures courses, but we can all use reminders now and again. Here are some that I think are useful:
I am very open to additional suggestions of resources that should be on this page, errata or improved or alternate versions of the resources listed about.