CS 598 TMC, Fall 2021

Topics in Computational Geometry

Lecture Time and Link

Tue & Thu 11:00am-12:15pm on zoom


Timothy Chan (tmc "at" illinois.edu)

office hours: Wednesdays at 2pm-3pm on zoom (email me if you want to meet at a different time, or meet in-person...)

Course Overview

Computational geometry is about the design and analysis of efficient algorithms for solving problems that involve geometric data or geometric objects. This course will cover selected topics in the area that I find theoretically interesting (occasionally touching on recent research).

No prior knowledge in computational geometry is assumed -- the only prequisite is a solid background in (and a love of) algorithms at the level of CS374 or equivalent. (But if you have taken Jeff's CS498 course last year, this course will be a good continuation, as the overlap of topics will be minimal.)

Possible topics include geometric data structures (e.g., orthogonal range searching, point location, nonorthogonal range searching), approximate nearest neighbor search and related problems, geometric approximation algorithms (e.g., independent set, set cover, traveling salesman), and combinatorial geometry (e.g., incidences, k-sets, Davenport-Schinzel sequences). Along the way, we will encounter many fun solutions and techniques (k-d trees, range trees, segment trees, fractional cascading, persistence, planar separators, random sampling, randomized incremental construction, cutting lemma, partition theorem, parametric search, quadtrees, Z-ordering, core sets, epsilon-nets, multiplicative weight update, local search, ...).

Course Work

(Assignments, presentations, and projects may be done individually or in groups of 2.)



(Scribbles from class, and links to relevant papers, will be provided below. For registered students, recordings of the zoom lectures may be accessed at mediaspace.)