CSE546: Computational Geometry (Fall 2017)

This course considers data structures and algorithms for spatial data sets, collections of points, lines, planes, polygons and polyhedra that live in 2 or 3 dimensional space. These data structures form the basis for modern work in Computer Graphics, Geographic Information Systems, and, to a lesser extent, Computer Vision and Machine Learning.

Time and location: T, Th 2:30-4pm in Duncker 101 .

Textbook: "Computational Geometry: Algorithms and Applications" , Third Edition. This textbook is required. It is a fantastic book, and relatively inexpensive. I also recommend reading Dave Mount's (wonderful) Lecture Notes.

Piazza: I encourage you all to post and answer questions on Piazza. While the TAs and I will try to be as responsive as we can, the collective wisdom of the class is a much better resource to explore.

Grading: Your grade depends on your performance on homework, exams, and (optionally) the final project. There will be four (4) homework and two (2) exams throughout the semester, all of which are completed individually in written form. The final project may involve programming and can be completed in a group of up to three people. Homeworks and exams have equal share in the final grade. Any submitted final project gets a perfect score, but its share in the final grade varies based on the difficulty of the project and how well it is done. The project's share may range between 0% and 40%. The actual formula can be found here. No late homeworks or projects are accepted.

Academic Integrity: You are required to be familiar with and follow the academic integrity policy, which is in turn similar to the policies of Jeremy Buhler in 441/541.

People and office hours
  • Instructor: Prof. Tao Ju (taoju at cse.wustl.edu)
    • Hours: Thursday 4p-5p (Jolley 406)
  • TAs: Rudy Zhou (rudyzhou1234 at gmail.com), John Xiahou (z.xiahou at wustl.edu), Jeffery Jung (jungjeffery at wustl.edu)
    • Hours: Monday 9:30a-11a, Friday 2:30p-4p, Wednesday 10a-11:30a (Jolley 408)

Voronoi Diagrams and Delauney triangulations: data structures to reason about points and regions in space.
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.

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)

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.