SUBJECT

Title

Geometric algorithms

Type of instruction

lecture

Level

master

Part of degree program
Credits

3

Recommended in

Semesters 1-4

Typically offered in

Autumn/Spring semester

Course description

Convex hull algorithms in the plane and in higher dimensions.

Lower bounds: the Ben-Or theorem, moment curve, cyclic polyhedron. Decomposition of the plane by lines. Search of  convex hull in the plane  (in higher dimensions), search of large convex polygon (parabolic duality) . Point location queries in planar decomposition. Post office problem. Voronoi diagrams and Delaunay triangulations and applications. Randomized algorithms and estimations of running times.

Readings

De Berg, Kreveld, Overmars, Schwartzkopf: Computational geometry. Algorithms and applications, Berlin, Springer  2000.