# This is an archived page and may be obsolete; the current pages are at http://www.iit.edu/csl/cs

# 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)