After completing the course, the student
-
Has knowledge of the most important techniques to develop geometric algorithms.
-
Has knowledge of the most important proof methods to determine the efficiency of geometric algorithms.
-
Knows about possible applications of geometric algorithms, like in robotics, graphics and geographic information science.
-
Knows how an applied problem can be converted into an abstract problem that can be tackled with techniques from computational geometry.
-
Knows how to apply the sweep-line technique correctly, including the use of status structure, event list, event handling, and efficiency analysis.
-
Knows how to apply the technique of randomized incremental construction for linear programming and minimum enclosing circle, inclusive of the probabilistic proof techniques needed.
-
Knows what the planar point location problem is and how it can be solved with randomized incremental construction.
-
Knows about kd-trees and range trees: definition, construction algorithms, and query algorithms. Also, performance of these algorithms.
-
Knows about Voronoi diagrams of points, Voronoi diagrams of line segments, furthest site Voronoi diagrams, and properties of these structures. Also, the sweep-line algorithm to construct them.
-
Knows about line segment intersection, map overlay, and polygon triangulation by a sweepline algorithm.
-
Can independently analyze a geometric problem by discovering properties that can lead to an algorithmic solution
-
Can analyze his/her solution on correctness and efficiency.
|
 |
|
|
In many areas of computer science (robotics, computer graphics and virtual reality, and geographic information systems are some examples) it is necessary to store, analyze, and create or manipulate spatial data. This course deals with the algorithmic aspects of these tasks: the design and analysis of geometric algorithms and data structures are studied.
|
|