CS 664: Algorithms in Combinatorial Geometry

Course Contents:

Basics: fundamental concepts in combinatorial geometry, permutation tables, semispaces of configurations, dissection of point sets, zones in arrangement, the complexity of families of cells.

Fundamental algorithms: constructing arrangements, skeletons in arrangements, linear programming, planar point location search.

Applications: problems for configurations and arrangements, separation and intersection in the plane.

Books and References:

H. Edelsbrunner.Algorithms in Combinatorial Geometry, Springer-Verlag, 1987.