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.

AMS 301; programming knowledge of C or C++ or Java

• Expose students to fundamental algorithms and structures in computational geometry, such as convex hulls, triangulation, Voronoi diagrams, and arrangements.
• Demonstrate applications of geometric algorithms in computer graphics, robotics, geographical information systems, and manufacturing.
• Reinforce the students' general knowledge in the design, analysis, and implementation of computer algorithms.

• Computational Geometry in C, Second Edition, By Joe O'Rourke, Cambridge University Press, 1998, ISBN 0-521-64976-5

• 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