Computational Geometry Notes

Please find below slides and notes for the courses, CS 164 and CS 266, Computational Geometry.

Notes:

• Week 1: Introduction and Convex hulls. Reading: Chapter 1 and the following:
  • Algorithm Analysis (Powerpoint)
  • Introduction (Powerpoint)
  • Convex hulls (Powerpoint)
  • Wikipedia article on Big-Oh notation
  • Wikipedia article on gift wrapping algorithm.
  • Divide-and-conquer convex hulls:
    • Some nice slides by Carola Wenk on the divide-and-conquer approach for convex hulls.
    • Wikipedia article on The Master Theorem for analyzing divide-and-conquer algorithms
  • Upper hull binary search. Reading Section 1-3 in the following paper gives the binary search method:
    • Overmars and van Leeuwen, Maintenance of Configurations in the Plane.
  • Mostly for CS 266 students: Chan's Simple Output-Sensitive Convex Hull Algorithm (Powerpoint)
  • Wikipedia article on Chan's Convex Hull algoriothm.
• Week 2: Line segment intersection. Reading: Chapter 2 and the following:
  • Wikipedia article on line-line intersections
  • Wikipedia article on the Bentley-Ottmann plane-sweep algorithm
  • Wikipedia article on WAVL Trees (a type of balanced binary search tree)
  • Zip trees (another type of (randomized) binary search tree)
  • Plane-sweep line segment intersection algorithm (Powerpoint)
  • Doubly-Connected Edge List, or DCEL (Annotated slides)
  • Overlaying planar subdivisions (Powerpoint)
• Week 3: Polygon triangulation and lower envelopes. Reading: Chapter 3 and the following:
  • Polygon triangulation ( Powerpoint) (Annotated slides)
  • Wikipedia article on polygon triangulation
  • Lower Envelopes (Powerpoint) [This subject is not in the textbook.]
  • Wikipedia article on Davenport-Schinzel sequences
• Week 4: Linear programming. Reading: Chapter 4 and the following:
  • Linear Programming ( Powerpoint)
• Week 5: Range searching. Reading: Chapter 5 and the following:
  • Range searching (Powerpoint)
  • Wikipedia article on range searching
  • Wikipedia article on range trees
  • Wikipedia article on fractional cascading
  • K-D trees (Powerpoint)
  • Wikipedia article on K-D trees
• Week 6: Point location. Reading: Section 6.1 (the rest of Chapter 6 is optional) and the following:
  • Planar point location (Powerpoint) [Most of this is not in the textbook]
  • Wikipedia article on point location
  • For all students, read: Planar point location using persistent search trees, by Sarnak and Tarjan
  • Wikipedia article on persistent data structures
  • Kirkpatrick's planar point location method (Powerpoint) [This subject is not in the textbook]
  • For all students, read: Optimal search in planar subdivisions, by Kirkpatrick
• Week 7: Voronoi diagrams. Reading: Chapter 7 and the following:
  • Voronoi diagrams and Their Applications (Powerpoint)
  • Constructing Voronoi diagrams (Powerpoint)
  • Wikipedia article on Voronoi diagrams
• Week 8: Arrangements and duality. Reading: Chapter 8 and the following:
  • Point-line duality (Powerpoint)
  • Line arrangements (Powerpoint)
  • Wikipedia article on line arrangements
• Week 9: Delaunay triangulations and 3D convex hulls. Reading: Chapter 9, Section 11.1, and the following:
  • Delaunay triangulations (Powerpoint)
  • Wikipedia article on Delaunay triangualtions
  • 3D Convex Hulls [these algorithms are not in the textbook]
• Week 10: Windowing data structures. Reading: Chapter 10 and the following:
  • Windowing data structures (Powerpoint)
  • Wikipedia article on segment trees
  • Wikipedia article on interval trees