Skip Navigation

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 2021 :

"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)


AMS 545 Instructor page

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.