Catalog 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.
Prerequisite: AMS 301 ; programming knowledge of C or C++
3 credits
Textbook: Computational Geometry in C, Joe OĠRourke, Second Edition, Cambridge Univ. Press
ISBN# 9780521649766
THIS COURSE IS TAUGHT IN THE SPRING SEMESTER IN 2009. IN FUTURE YEARS IT WILL BE TAUGHT IN THE FALL SEMESTER ONLY.
Introduction to Computational Geometry: 2 hours
Simple polygons, visibility, art gallery theorem: 4 hours
Triangulating polygons, plane sweep algorithm: 9 hours
Convex hulls in the plane: 5 hours
Review and Midterm: 3 hours
Polyhedra and convex hulls in 3D: 3 hours
Voronoi and Delaunay diagrams, proximity: 4 hours
Arrangements of lines and duality: 3 hours
Segment intersection search: 3 hours
Point location search: 2 hours
Review and test: 4 hours