Textbook in PDF format

This is an introductory course on computational geometry and its applications. We will discuss techniques needed in designing and analyzing efficient algorithms and data structures for computational problems in discrete geometry, such as convex hulls, geometric intersections, geometric structures such as Voronoi diagrams and Delaunay triangulations, arrangements of lines and hyperplanes, and range searching.
Preliminaries: Basic Euclidean geometry
Hulls: Convex hull algorithms (Graham's algorithm, Jarvis's algorithm, Chan's algorithm)
Linear Programming: Half-plane intersection, point-line duality, randomized LP, backwards analysis, applications of low-dimensional LP
Intersections and Triangulation: Plane-sweep line segment intersection, triangulation of monotone subdivisions, plane-sweep triangulation of simple polygons
Point Location: Trapezoidal decompositions and analysis, history DAGs
Voronoi Diagrams: Basic definitions and properties, Fortune's algorithm
Delaunay Triangulations: Point set triangulations, basic definition and properties, randomize incremental construction and analysis
Arrangements and Duality: incremental construction of arrangements and the zone-theorem, applications
Geometric Data Structures: kd-trees, range trees and range searching, segment trees
Geometric Approximation: Dudley's theorem and applications, well-separated pair decompositions and geometric spanners, VC dimension, epsilon-nets and epsilon-approximations
Computational Topology: Simplicial complexes, continuous maps and homeomorphisms, review of algebra and homology, nerves, filtrations, applications to shape analysis