COL752
| COL752 | |
|---|---|
| Geometric Algorithms | |
| Credits | 4 |
| Structure | 3-0-2 |
| Pre-requisites | COL351 OR Equivalent |
| Overlaps | |
COL752 : Geometric Algorithms
[edit]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. Courses of Study 2024-2025 Computer Science and Engineering 164