Time: TH 3-4:20 PM
Location: 100 Tureaud Hall
Instructor: Avah Banerjee
Office Hours: TH 4:30-5:30 PM (Location TBA)
Email: ibanerjee@lsu.edu
Course website: cct.lsu.edu/~ibanerjee/csc4700.html
Prerequisites
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.
Textbook:
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%