Mount D. Computational Geometry. CMSC 754 2023

Download this torrent!

Mount D. Computational Geometry. CMSC 754 2023

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