CSE546: Computational Geometry (Spring 2014)

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 Green Hall L0160.

Textbook: "Computational Geometry: Algorithms and Applications" , Third Edition. This textbook is required. It is a fantastic book, and relatively inexpensive. The Second or First edition of the textbook is acceptable. 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 the final project. There will be four (4) homework and two (2) exams throughout the semester, all of which are completed in written form. The only assignment that requires programming is the final project, which is turned in at the end of the semester. See more details in the sections below.

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

Office hours
  • Prof. Tao Ju (taoju at cse.wustl.edu): Thursday 4-5pm (Jolley 406)
  • Yajie Yan (yajieyan at wustl.edu): Monday 1:30-2:30pm, Wednesday 4:30-5:30pm (Jolley 426)
New: Course project specification is here. If you choose to do it, it is due May 4th.

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.

Most lectures closely follow either the textbook (the "Book") or Dave Mount's notes (the "Notes"). Relevant locations in these materials are noted.

  • Lecture 1: Introduction (Slides) and convex hulls (Notes: Lecture 1 and first part of Lecture 3; Book: Chapter 1)
  • Lecture 2: 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 (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)
  • Lecture 8: Kirkpatrick's point location algorithm (Notes: Lecture 25)
  • 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 (Feb 25th)
  • 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, applets for alpha hulls and furthest-point Voronoi diagrams, additively weighted Voronoi diagrams, and power diagrams)
  • 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)
  • Guest lecture: Nearest neighbors in high dimensions (by Jeremy Buhler, notes)
  • Lecture 22: Interval trees (Notes: Lecture 24; Book: Chapter 10.1)
  • Lecture 23: Shortest paths and visibility graphs (Notes: Lecture 21; Book: Chapter 15)
  • Lecture 24: Motion planning (Notes: Lecture 22; Book: Chapter 13)
  • EXAM 2 (Apr 22nd)
  • Video day! (list of videos, archive of videos accepted to SoCG)

You have 2 weeks for completing each homework, which should be turned in before class on the noted dates. 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 by the problem):
  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 May 4th.

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.