CS 498TC, Spring 2018: Computational Geometry


Timothy Chan (tmc, Siebel 3230, office hours: Wed 3:30-4:30 & Fri 3:30-4:30 or by appointment)

Meeting time/place

Wed & Fri 2:00-3:15, Siebel 1109

Course Work


  • Course policies
  • Academic integrity
  • Piazza

    Course Overview

    We will study efficient algorithms for a variety of fundamental geometric problems: convex hulls, Voronoi diagrams/Delaunay triangulations, low-dimensional linear programming, line segment intersection, polygon triangulation, geometric shortest paths, visibility, etc. Computational geometry has applications to many areas (geometric data are everywhere), although the focus of the course is on theoretical results and techniques (we will encounter lots of cool algorithmic ideas, including divide-and-conquer, prune-and-search, randomization, plane sweep, etc.). A solid background in algorithm design and analysis is assumed (at the level of CS374).


    There is no required textbook, but you may find the following useful:


    (I'll provide copies of my handwritten notes below...)

    Jan 17, 19, 24, 26: Convex hull in 2D

    Jan 31: Applications of convex hulls

    Feb 2, 7, 9: Convex hulls in 3D

    Feb 14, 16, 21: Voronoi diagrams and Delaunay triangulations

    Feb 23, 28, Mar 2: Linear programming in low dimensions

    Mar 7, 9, 14: Line segment intersection and arrangements

    Mar 16, 28: Point location

    Mar 30: Polygon triangulation

    Apr 4, 6: Applications of polygon triangulation

    Apr 11, 13, 18: Range searching Apr 20: BSP trees Apr 25, 27: Klee's measure problem May 2: Lower envelopes of line segments