Credits: 4 (3-0-2)
Prerequisites: COL351 OR Equivalent
Description
Geometric Fundamentals: Models of computation, lower bound techniques, geometric primitives, geometric transforms Convex hulls: Planar convex hulls, higher dimensional convex hulls, randomized, output-sensitive, and dynamic algorithms, applications of convex hull, Intersection detection: segment intersection, line sweep, map overlay, halfspace intersection, polyhedra intersection, Geometric searching: segment, interval, and priority-search trees, point location, persistent data structure, fractional cascading, range searching, nearest-neighbor searching Proximity problems: closest pair, Voronoi diagram, Delaunay triangulation and their subgraphs, spanners, well separated pair decomposition Arrangements: Arrangements of lines and hyperplanes, sweep-line and incremental algorithms, lower envelopes, levels, and zones, applications of arrangements Triangulations: monotone and simple polygon triangulations, point-set triangulations, optimization criteria, Steiner triangulation, Delaunay refinement Geometric sampling: random sampling and ε-nets, ε-approximation and discrepancy, cuttings, coresetsGeometric optimization: linear programming, LP-type problems, parametric searching, approximation techniques. Implementation Issues: robust computing, perturbation techniques, floating-point filters, rounding techniques.
Prerequisite Tree
flowchart TD
COL752-210[COL752]
COL106-210 --> COL100-210[COL100]
COL351-210 --> COL106-210[COL106]
COL752-210 --> COL351-210[COL351]
classDef empty height:17px, fill:transparent, stroke:transparent;
classDef trueEmpty height:0px, width:0px;