CS661 Geometric Algorithms: Learning Objectives & Outcomes

CS 661 Geometric Algorithms: Learning Objectives & Outcomes

CS 661 Geometric Algorithms
Learning Objectives:

Understand algorithms and their complexity for computing convex hulls
Understand the issues of degeneracy and robustness in geometric computation
Understand algorithms and their complexity for computing line segment intersection
Understand the use of the doubly-connected edge list
Understand algorithms and their complexity for computing overlays
Understand algorithms and their complexity for computing monotone partitions of polygons
Understand algorithms and their complexity for computing triangulation of monotone polygons
Understand algorithms and their complexity for computing half-plane intersections
Understand algorithms and their complexity for incremental linear programming
Understand algorithms and their complexity for randomized linear programming
Understand algorithms and their complexity for 1-D range searching
Understand the use of the Kd-tree and the range tree, also in higher dimensions
Understand algorithms and their complexity for fractional cascading
Understand algorithms and their complexity for point location with trapezoidal maps
Understand randomized and incremental algorithms and their complexity for point location
Understand algorithms and their complexity for computing Voronoi diagrams
Understand algorithms and their complexity for computing Voronoi diagrams of line segments
Understand algorithms and their complexity for computing farthest-point Voronoi diagrams

Learning Outcomes (Assessment):

Exams in the course provide direct feedback on understanding of concepts and
use of algorithms and data structures
Projects in the course exercise practical applications
For this material, which carries many useful elements, the ability to recognize
where those elements can be applied in other computer science work indicates success as well