AMS 345, Computational Geometry
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++ or Java
3 credits
Required Textbooks:
"Computational Geometry in C" by Joseph O'Rourke, 2nd Edition, Cambridge Univ. Press,
2008; ISBN# 9780521649766; and
"Discrete and Computational Geometry" by Devadoss and O'Rourke, 2011; ISBN: 9780691145532
/ 0691145539
Optional Textbook:
"Computational Geometry: Algorithms and Applications" by de Berg, Cheong, van Kreveld,
and Overmars, 3rd edition, Springer-Verlag, 2008; ISBN 978-3-540-77973-5
THIS COURSE IS TAUGHT IN THE FALL SEMESTER ONLY.
Learning Outcomes for AMS 345, Computational Geometry:
1) Demonstrate an understanding of the geometry, combinatorics, and computation of
discrete geometric structures including:
* convex hulls of finite point sets in two and three dimensions;
* simple polygons, polygonal domains, planar straight-line graphs, special
classes of polygons (monotone, star-shaped, etc.);
* visibility and visibility coverage of polygons, including the Art Gallery
Theorem;
* triangulations and convex decompositions of point sets and planar polygonal
domains;
* planar graph properties that apply to the combinatorial analysis of geometric
decompositions;
* Delaunay diagrams and related proximity graphs on finite point sets in the
Euclidean plane (Euclidean minimum spanning trees, nearest neighbor graphs, relative
nearest neighbor graphs, Gabriel graphs);
* Voronoi diagrams;
* arrangements of lines in the plane;
* geometric duality, including point-line duality in the plane and its application
to problem solving.
2) Demonstrate an understanding of the design and analysis of algorithms to solve
algorithmic problems with geometric data:
* learn to think algorithmically and to formulate precise algorithmic problems;
* perform worst-case analysis of an algorithm in the language of big-Oh notation;
* learn to develop precise algorithmic models of problems that arise in data
analysis, interactions with the physical world, engineering, and operations research;
* understand and utilize algorithmic paradigms in the design and analysis
of discrete algorithms, including divide-and-conquer, plane sweep, incremental insertion,
and hierarchical methods;
* understand how primitive computations are done on geometric data using principles
of vector analysis and analytic geometry;
* understand the use of geometric data structures for segment intersection,
triangulation, convex hull computation, and point location search.