Course Details

  • Course Number: 16:198:529
  • Course Type: Graduate
  • Semester 1: Fall
  • Credits: 3
  • Description:

    Computational geometry addresses geometric questions using ideas from algorithms, data structures, complexity theory, and combinatorics. As such, it provides a nice set of applications from these disciplines and also contains features that are interesting and useful in their own right. The aim of this course is to provide the student with a solid foundation in the field.
  • M.S. Course Category: Algorithms & Complexity
  • Category: A (M.S.), A (Ph.D.)
  • Prerequisite Information:

    16:198:513 OR 16:198:512 (16:198:514 is recommended)
  • Course Links: 16:198:512 - Introduction to Data Structures and Algorithms, 16:198:513 - Design and Analysis of Data Structures and Algorithms
  • Topics:

        *  Geometric objects and data structures
        * Convex hulls in the plane and higher dimensions
        * Lower bound proofs
        * Arrangements of lines, plane sweep, duality
        * Decomposition and partitioning
        * Searching and planar point location
        * Voronoi diagrams and Delaunay Triangulations
        * Farthest-pair and closest-pair problems
        * Geometric Optimization and Linear Programming
        * algorithmic paradigms coming from Comp. Geom.: randomized, incremental algs.; parametric search.

    Course Material: 

    Suggested Text: "Computational Geometry: Algorithms and Applications", Third Ed., Mark de Berg, Mark van Kreveld, Mark Overmars, Ottfried Schwartzkopf, Springer, New York, 2008.
  • Expected Work: Weekly reading, a problem set, an examination, a project (paper presentation; on rare occasion, implementation projects were allowed).
  • Exams: The usual practice is a take-home exam.
  • Learning Goals:

    The aim of this course is to provide the student with a solid foundation in the field, and to show some of the many applications of Computational Geometry.