COMS 5180: Introduction to Computational Geometry
(Dual-listed with COMS 4180).
Credits: 3. Contact Hours: Lecture 3.
Introduction to data structures, algorithms, and analysis techniques for computational problems that involve geometry. Convex hulls, line segment intersection, polygon triangulation, 2D linear programming, range queries, point location, arrangements and duality, Voronoi diagrams, Delaunay triangulations, geometric data structures, robot motion planning, visibility graphs. Other selected topics. Programming assignments. Scholarly report required for graduate credit.