CSE355

Course	CSE355
Title	Computational Geometry
Credits	3
Course Coordinator	Joseph S. B. Mitchell
Description	The design and analysis of efficient algorithms to solve geometric problems that arise in computer graphics, robotics, geographical information systems, manufacturing, and optimization. Topics include convex hulls, triangulation, Voronoi diagrams, visibility, intersection, robot motion planning, and arrangements. This course is offered as both AMS 345 and CSE 355. Bulletin Link
Prerequisite	Prerequisites: AMS 301; programming knowledge of C or C++ or Java
Course Outcomes	An understanding of the fundamental algorithms and structures in computational geometry, such as convex hulls, triangulation, Voronoi diagrams, and arrangements. An ability to apply geometric algorithms in computer graphics, robotics, geographical information systems, and manufacturing. A working knowledge of design, analysis, and implementation of computer algorithms.
Textbook	Satyan L. Devadoss, Joseph O'Rourke, Discrete and Computational Geometry, Princeton University Press, 2011. Joseph O'Rourke, Computational Geometry in C, 2nd ed., Cambridge University Press, 1998.
Major Topics Covered in Course	Polygons, triangulation, visibility, art gallery problems Convex hulls in two and higher dimensions Proximity problems: closest pair, closest point queries Voronoi diagrams, Delaunay diagrams Geometric minimum spanning trees, traveling salesman problem Arrangements of lines, hyperplanes; geometric duality Intersection problems; Bentley-Ottmann sweep Point location search
Laboratory	N/A
Course Webpage	CSE355