Computational Geometry

CS 498 TC, Spring 2021

Main    Syllabus    Schedule    Resources


Brain Dump

This is just a brainstorming list, with an attempted resolution of one lecture per bullet. Don't take ordering too seriously. There are a total of 28 class periods in the schedule. If I allocate one for the midterm, two for Wednesday instructional breaks, and one for student presentations, that leaves room for 24 lectures. Ha ha yeah right.
  1. Models of computation: and models
  2. Basic primitives
  3. Point in polygon, winding number
  4. Planar convex hulls:
  5. Rotating calipers (diameter)
  6. Higher-dimensional convex hulls:
  7. Line segment intersection (sweep line)
  8. Trapezoidal decomposition
  9. Polygon triangulation
  10. Point location
  11. Shortest paths and ray shooting
  12. BSP trees
  13. Line arrangements
  14. 3SUM-hardness
  15. Voronoi + Delauany
  16. Fixed-dimensional linear programming
  17. Orthogonal range searching
  18. Quadtrees + Octtrees
  19. Maxwell–Cremona correspondence
  20. Well-separated pair decompositions
  21. Simplex range searching (oof)
  22. Kinetic data structures
  23. Fréchet distance (and variants)
  24. Translational motion planning