CSC 4700 Computational Geometry (Fall 2019)

Time: TH 3-4:20 PM
Location: 100 Tureaud Hall

Instructor: Avah Banerjee
Office Hours: TH 4:30-5:30 PM (Location TBA)
Course website:

CSC 3120 or equivalent or permission from the instructor. Students are expected to have an understanding of basic algorithm design techniques and data structures.

Course description:
Many real and virtual applications deal with geometric data. Computational Geometry (CG) is the formal study of problems arising in such applications. This will be an introductory course in CG. We will discuss tools and techniques needed to design and analyze algorithms and data structures to solve geometric problems. We will cover convex hulls, arrangements of points and hyperplanes, voronoi diagrams, range searching etc.

De Berg, M., Van Kreveld, M., Overmars, M., & Schwarzkopf, O. (1997). Computational geometry 3rd Edition.

Tentative List Topics:
1. Introduction/ Preliminaries
2. Convex hulls/ maximals layers
3. Triangulations
4. Voronoi Diagrams
5. Arrangements and duality
6. Robot motion planning and Visibility
7. Geometric data-structures and searching
8. Approximation algorithms

Grading (tentative):
1. Homework : 40%
2. Project* : 30%
3. Paper Reading + presentation and class participation: 30%