Introduction: Historical perspective, Geometric preliminaries. Convex hulls algorithms in 2D and 3D, lower bounds.
Triangulations: Polygon triangulations, Representations, Point-set triangulations. Voronoi diagrams: Algorithms,
Closest pair problems. Delaunay triangulations: algorithms (divide-and-conquer, flip, incremental), Duality of
voronoi diagrams, Properties (min-max angle). Geometric searching: Point-location, 2D linear programming with
prune and search. Visibility: Algorithms for weak and strong visibility, Visibility with reflections, Art-gallery
problems. Arrangements of lines: 2D arrangements, zone theorem, Many-faces complexity, algorithms. Sweep
techniques: Plane sweep for segment intersections, Fortune's sweep for Voronoi diagrams, Topological sweep for line
arrangements. Combinatorial geometry: Ham-sandwich cuts, Helly's theorems, k-sets. Rectilinear geometry:
Intersection and union of rectangles, Rectangle searching. Robust geometric computing. Applications of
computational geometry.