Introduction to Computational Geometry

COM S 418
  1. Credits and contact hours: 3 credits, 3 contact hours
  2. Instructor’s or course coordinator’s name: Yan-Bin Jia
  3. Text book, title, author, and year: M. de Berg, O. Cheong, M. van Kreveld, and M. Overmars. Computational Geometry: Algorithms and Applications (3rd edition). Springer-Verlag, 2008. ISBN: 978-3-642-09681-5.
  4. Other supplemental materials, a website that provides additional material such as pointers to software and research papers.

Specific course information

  1. Brief description of the content of the course: Introduction to data structures, algorithms, and analysis techniques for computational problems that involve geometry. Convex hulls, line segment intersection, polygon triangulation, 2D linear programming, range queries, point location, arrangements and duality, Voronoi diagrams, Delaunay triangulations, geometric data structures, robot motion planning, visibility graphs. Other selected topics. Programming assignments.
  2. Prerequisites or co-requisites: COM S 311 or permission of instructor
  3. Required, elective, or selected elective? Selected Elective

Specific goals for the course

  1. Specific outcomes of instruction:
  • An ability to design, implement, and evaluate a computing-based solution to meet a given set of computing requirements in the context of the program’s discipline (2)
  • An ability to apply computer science theory and software development fundamentals to produce computing based (6)

Brief list of topics to be covered

  • 2D convex hulls
  • Line segment intersection
  • Doubly-connected edge list
  • Overlay of planar subdivisions
  • Polygon triangulation
  • Half-plane intersection
  • Incremental and randomized linear programming
  • Orthogonal range searching
  • Kd-trees and range trees
  • Point location and trapezoidal maps
  • Voronoi diagrams
  • Duality and line arrangements
  • Delaunay triangulation
  • 3D convex hulls and half-space intersection
  • Robot motion planning
  • Visibility graphs
  • Interval trees and segment trees