CS 533: Computational Geometry

Objectives

• Computational geometry addresses data structures and algorithms for solving geometric problems.
• Geometric problems arise in a number of applications including Geographic Information Systems, Graphics, Robotics, Numerical methods, Bio-Informatics etc.
  • Consider Geographic Information Systems.
  • Common problems in this domain include determining the closest facility to a given query point, facility location itself, shortest path computations.
  • In the context of Graphics, common problems include ray-shooting to determine the first object in the line of sight, space-partitioning to represent objects and object sets etc.
• The course will introduce techniques to deal with problems arising from these applications. The course will comprise of both fundamental algorithms as well as applications.

Prerequisites

• CS 430 and a Linear Algebra course.

Syllabus

• Convex hulls
• Voronoi diagrams
• Delaunay triangulations
• Euclidean Minimum Spanning Trees with application in clustering
• Geometric algorithms for Linear programming
• Range Searching with database applications
• Point location
• Combinatorial geometry of arrangements
• Shortest paths with applications in Robotics
• BSP-trees and applications in graphics.

Edited March 2006 (html, css checks)