CIS 677: Computational Geometry

CIS 677: Computational Geometry


Name: Ken Clarkson
Phone: 908 582 4717
Office, and hours:

  • from 11-12 before class, Prof. Sampath Kannan's office.
  • after class, the theory lab.


Time: Mondays, Noon-3
Location: Towne 321


CIS 502 or equivalent


  • Four homework assignments (roughly)
  • One term paper or programming project; suggestions


M. de Berg, M. van Kreveld, M. Overmars, O. Schwarzkopf. Computational Geometry: Algorithms and Applications. Springer, ISBN 3-540-61270.

Reference Books

Some of the following will be on reserve at the library:

Lectures and homework

Course Synopsis

Here are some things I'd like to talk about, requiring somewhere between half and twice the available time. Starred topics are a bit less likely to be covered.

An introduction via planar convex hulls

Coordinate-wise dominance, orthogonal range queries

Planar subdivisions

Planar point location

Voronoi diagrams, Delaunay triangulations, convex polytopes

Low-dimensional linear programming and optimization

*Helly properties

Simplex range searching, VC dimension

Geometric search trees

Geometric graph problems

Degeneracy and robustness

Ken Clarkson
August 1997