Computational Geometry

Convex hull in 2, 3 and higher dimensions, gift-wrapping, divide and conquer, incremental algorithm and volume computation. Worst-case and output sensitive complexity, lower bounds, upper bound theorem on convex hull size, geometric duality. Linear programming, Simplex algorithm, randomized algorithms and expected complexity. Voronoi diagram, sweep method, Delaunay triangulations, connection with convex hull. Triangulation of point-set in two and more dimensions, triangulation of simple polygon and the art gallery problem, visibility in the plane. Vertical subdivision, point location, nearest neighbor, geometric data structures and geometric searching. Arrangements of lines and line segments. Implementation issues, degeneracy, input perturbation. Applications to robot motion planning, to macromolecular structure, to computer-aided design and graphics. Geometric implementations using the geometry software library CGAL or Python.