Academics / Courses / DescriptionsCOMP_SCI 396, 496: Computational Geometry
VIEW ALL COURSE TIMES AND SESSIONS
Prerequisites
Mathematical Foundations of Computer Science (COMP_SCI 212) and Data Structures (COMP_SCI 214). I also highly recommend having taken Design and Analysis of Algorithms (COMP_SCI 336).Description
Computational geometry is the study of designing and analyzing algorithms that solve geometric problems. In this class, we will study geometric objects (such as convex hulls, Voronoi Diagrams, and Delaunay Triangulations), geometric data structures (such as kd-trees and range trees), geometric problems (such as line segment intersection and the art gallery problem), and techniques for designing geometric algorithms (such as incremental algorithms and plane-sweep algorithms). We will simultaneously look at the enumerable applications of computational geometry to areas as diverse as computer graphics (e.g. collision detection), databases (e.g. orthogonal range search), machine learning (e.g. nearest-neighbor search), optimization (e.g. linear programming), and robotics (e.g. motion planning).
We will focus on rigorously analyzing the correctness and time complexity of our algorithms. Time permitting, we may also look at additional topics in high-dimensional geometry.
- Fulfills CS Technical Elective requirement
INSTRUCTOR: Huck Bennett
REQUIRED TEXTBOOK: "Computational Geometry: Algorithms and Applications" Third Edition by Mark de Berg, Otfried Cheong, Marc van Kreveld, and Mark Overmars.