Special Topics in Theory: Computational Geometry
Course ID 15859
Description This course aims to provide an introduction to computational geometry and numerical computation to those with some background in algorithms and geometry. Focus will be in low, especially 2, dimensions. Main topics are plane sweeps, convexity, geometric construction/optimization, optimization algorithms in low to intermediate dimensions, and geometric data structures. Evaluations will consist of 5 homework and a final exam, and will be flexible to allow both theoretical and implementation perspectives.
Key Topics
geometry, seminumerical algoirthms, data structures
Required Background Knowledge
some exposure to algorithms and geometry in 2-D
Course Relevance
Students with interest in either theory or numerical computation. Course will be taught assuming some familiarity with introductory 2-D Euclidean geometry, combinatorial graphs, and worst-case analysis of algorithms. Some of the optional topics will need knowledge of data structures, high performance coding, and combinatorial optimization.
Course Goals
Can systematically reason about the correctness and efficiency of geometric algorithms. Some familiarity with how to design and implement such algorithms.
Learning Resources
https://www.amazon.com/Computational-Geometry-Applications-Mark-Berg/dp/3540779736
Assessment Structure
5 hw 60% (drop lowest), final 40%
Extra Time Commitment
n/a