Charles Explorer logo

Introduction to Combinatorial and Computational Geometry

Class at Faculty of Mathematics and Physics |


Basic theorems on convex sets (Helly, Radon, Caratheodory, separation).

Minkowski's theorem on lattice points in convex bodies.

Line-point incidences.

Geometric duality. Convex polytopes: definition, basic properties, maximum number of faces.

Voronoi diagrams.

Hyperplane arrangements.

Arrangements of algebraic surfaces, pseudolines.


Discrete geometry investigates combinatorial properties of geometric objects such as finite point sets or convex sets in Euclidean spaces.

Computational geometry considers the design of efficient algorithms for computing with geometric configurations, and discrete geometry serves as its mathematical foundation.

Part I of the course is a concise introduction. The contents of Part II varies among the years, each year covering a few selected topics in more depth.