AMS 545, Computational Geometry
Study of the fundamental algorithmic problems associated with geometric computations,
including convex hulls, Voronoi diagrams, triangulation, intersection, range queries,
visibility, arrangements, and motion planning for robotics. Algorithmic methods include
plane sweep, incremental insertion, randomization, divide-and-conquer, etc. This course
is offered as both AMS 545 and CSE 555.
3 credits, ABCF grading
Textbooks for Spring 2024:
"Computational Geometry: Algorithms and Applications" by Marc Van Kreveld, Mark De
Berg, Mark Overmars, Otfried Cheong, 3rd edition, Publisher: Springer-Verlag New York Inc; ISBN: 9783540779735 (Required)
"Computational Geometry in C", by Joseph O'Rourke, 2nd edition, Cambridge University Press; ISBN: 978-0521649765 (Recommended)
"Discrete and Computational Geometry", by Devadoss & O'Rourke, 2011, Princeton University Press; ISBN: 978-0691145532 (Recommended)
Learning Outcomes:
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 within polyhedral domains and visibility coverage of polygons,
including the Art Gallery Theorem;
* Triangulations and convex decompositions of point sets and planar polygonal
domains;
* Delaunay diagrams and Voronoi diagrams on finite point sets in low dimensions,
according to the Euclidean metric and other metrics;
* Proximity graphs, including Euclidean minimum spanning trees, nearest neighbor
graphs, relative nearest neighbor graphs, Gabriel graphs;
* Arrangements of lines and line segments in the plane;
* Arrangements of hyperplanes in higher dimensions;
* Principles of geometric duality, including point-line duality in the plane,
point-hyperplane duality in higher dimensions, and their applications to algorithmic
problems;
* Lower envelopes and their connection to Davenport-Schinzel sequences.
2) Demonstrate an understanding of the design and analysis of algorithms to solve
algorithmic problems with geometric data:
* Develop algorithmic thinking and the careful formulation of precise algorithmic
problems;
* Perform worst-case and average-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;
* Design and analyze randomized algorithms for solving geometric problems;
* 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, halfspace intersection, low-dimensional linear
programming, range search, point location search, and robot motion planning.