## TTIC 31100 / CMSC 39000 Computational geometry

**Autumn quarter, 2010.**

**Intructors:**
Yury Makarychev,
Anastasios Sidiropoulos.

**Time:**
Tue & Thu, 10:30-11:50.

**Location:**
Toyota Technological Institute, 6045 S. Kenwood Ave., Room 530.

### Description

The course covers fundamental concepts and algorithms in computational geometry. Topics covered include: convex hulls, polygon triangulations, range searching, segment intersection, Voronoi diagrams, Delaunay triangulations, motion planning, binary space partitions, geometric polynomial-time approximations schemes, locality-sensitive hashing, metric embeddings and applications.

### Textbooks

The course textbooks are *Computational geometry* by M. de Berg, O. Cheong, M. van Kreveld, M. Overmars, and *Lectures on discrete geometry* by J. Matousek.

### Requirements

There will be 4-6 homework assignments.

### Problem sets

Problem set 1.
Posted: Oct 7, 2010,
due: Oct 21, 2010.

Problem set 2.
Posted: Oct 20, 2010,
due: Nov 4, 2010.

Problem set 3.
Posted: Nov 8, 2010,
due: Nov 18, 2010.

Problem set 4.
Posted: Nov 18, 2010,
due: Nov 30, 2010.