COMP_SCI 396, 496: Computational Geometry

Quarter Offered

Winter : TuTh 11-12:20 ; Bennett


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).


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.