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

**Topics**:

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.