Data structures for storing geometric objects. Deterministic methods for manipulation of point sets, Divide-and-conquer, sweeping. Closest pair, furthest pair. Random sample methods. Sample theorem, moment theorem. Probabilistic algorithms, online algorithms, dynamic algorithms. Convex hull, polytopes. Various incremental algorithms for finding the convex hull of a set of points. Convex hull in 2 dimensions, relation to array sorting. Convex hull of a set of balls. Smallest enclosing ball containing given points. Triangulations in 2 dimensions, with or without restrictions. Delaunay triangulation, triangulations in 3 dimensions. Simplices and complexes. Art gallery problems. Binary space partitions. Painter’s algorithm. Quadtrees and octrees. Hyperplane arrangements, discrepancy. Zone Theorem. Line arrangements in the plane, duality, and arrangements of segments in the plane.