Geometric Algorithms

COMPCI 634 - Spring 2022

Instructor: Pankaj K Agarwal

TA: Erin Taylor

Time: TuTh 1:45-3:00

Location: LSRC D106

The field of Geometric Algorithms studies the design, analysis, and implementation of algorithms and data structures for geometric problems. These problems arise in a wide range of areas, including robotics, computer graphics, molecular biology, GIS, spatial databases, sensor networks, and machine learning. In addition to the tools developed in computer science, the study of geometric algorithms also requires ideas from various mathematical disciplines, including combinatorics, topology, and algebra.

The goal of this course is to provide an overview of the techniques developed in geometric algorithms as well as some of its application areas. The topics covered in the course will include:

- Geometric Fundamentals: Motivation, models of computation, geometric primitives, geometric transforms
- Convex hulls: Planar convex hulls, higher dimensional convex hulls, output-sensitive and dynamic algorithms
- Intersection detection: Segment intersection, line sweep, randomized incremental algorithm
- Geometric data structures: Segment and interval trees, point location, persistent data structure, orthogonal range searching, nearest-neighbor searching, geometric cuttings, simplex range searching
- Proximity problems: Voronoi diagram, Delaunay triangulation and their subgraphs, spanners, well separated pair decomposition
- Arrangements: Arrangements of lines and hyperplanes, sweep-line and incremental algorithms, lower envelopes, levels, and zones, union of objects, applications
- Geometric sampling: Random sampling and e-nets, e-approximation and discrepancy, coresets
- Geometric optimization: Linear programming, LP-type problems, shape matching, clustering
- High-dimensional geometry: Bourgain's theorem, random-projection, low-distortion embeddings, locality sensitive hashing

The main textbook for this course: M. de Berg, O. Cheong, M. van Kreveld, and M. Overmars, Computational Geometry: Algorithms and Applications. Springer-Verlag, 3rd ed., 2008.

Assignments: 40% weight

Four assignments will be given during the semester, which each student has to complete individually without searching the material online.

Lecture Scribe: 10% weight

Each student will scribe one lecture.

Research Project: 50% weight

Intended to produce a work of publishable quality, the project should consist of a comprehensive survey on a topic plus new research work. Due on April 20, 2022.

Sakai:

Accessed here. This works as the hub to Gradescope and Ed. Any course resources (e.g. lecture notes, solutions) will be hosted on Sakai under Resources.

Gradescope:

Accessed via Sakai. All assignments and project documents will be submitted here. See Assignments for more info.

Ed Discussions:

Accessed via Sakai. Ed is a questions-and-answers message board (similar to Piazza) that is easy to use and allows for all participants to help answer each other's questions. Please ask all course-related questions on Ed by creating a new post, not only those about assignments.