Joseph S. B. Mitchell

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

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

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

• 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

N/A

CSE355