Skip Navigation

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.

PrerequisiteAMS 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



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.

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.