Courses
Spring 2024
CS514 – Design and Analysis of Data Structures and Algorithms II
ARC 205 Tuesday 12:10-3:10pm.
Geometric Algorithms
In this course we consider geometry broadly defined, starting from algorithms that handle points, lines, polygons, etc, and move on to geometric structures embedded in physical spaces and real-world data and applications. In terms of algorithms we ask questions such as why classical optimization problems in a geometric setting are easier, what geometric properties can one define on a graph and how that can help with problem solving. We will discuss problems that involve distances, dimensionality and navigation. We also move beyond the notions of geometry (i.e., coordinates, distances, shapes) and talk about topology (connectivity, holes, voids). Students are expected to have a solid algorithm foundation and no background in computational geometry is assumed.
Sample topics:
- Convexity, Radon Lemma, Helly Theorem
- Low-dim LP and LP-type problems
- Power of Grid, linear time closest pair, Locality sensitive hashing
- Grid with random shifts, unit disk cover
- VC-dimension, eps-net and eps-approximation
- Geometric set cover, reweighting techniques
- (Euclidean) dimension reduction, MDS, Johnson Linderstrauss Lemma
- (Non-Euclidean) dimension reduction, Isomap,
- Bourgain theorem, embedding intro tree metrics
- Graphs of bounded doubling dimension
- Kleinberg’s small world model, greedy navigation, distance estimation
- Quad tree, well-separated pair decomposition
- Geometric spanners
- Geometric intersection graphs, planar graphs