SUBJECT
Geometric algorithms
lecture
master
3
Semesters 1-4
Autumn/Spring semester
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.
De Berg, Kreveld, Overmars, Schwartzkopf: Computational geometry. Algorithms and applications, Berlin, Springer 2000.