CS60064: Computational Geometry
| CS60064 | |||||||||||||||||||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| Course name | Computational Geometry | ||||||||||||||||||||||||||||
| Offered by | Computer Science & Engineering | ||||||||||||||||||||||||||||
| Credits | 3 | ||||||||||||||||||||||||||||
| L-T-P | 3-0-0 | ||||||||||||||||||||||||||||
| Previous Year Grade Distribution | |||||||||||||||||||||||||||||
| |||||||||||||||||||||||||||||
| Semester | Spring | ||||||||||||||||||||||||||||
Syllabus
Syllabus mentioned in ERP
Introduction: historical perspective, geometric preliminaries. Convex hulls algorithms in 2d and 3d, lower bounds. Triangulations: polygon triang-ulations, representations, point-set triangulations. Voronoi diagrams: algorithms, closest pair problems. Delayney triangulations: algorithms (divide-and-conquer, flip, incremental), duality of Voronoi diagrams, properties (min-max angle). Geometric searching: point-location, 2d linear programming with prune and search. Visibility: algorithms for weak and strong visibility, visibility with reflections, art-gallery problems. Arrangements of lines: 2d arrangements, zone theorem, many-faces complexity, algorithms. Sweep techniques: plane sweep for segment intersections, Fortune s sweep for Voronoi diagrams, topological sweep for line arrangements. Combinatorial geometry: Ham-sandwich cuts, Helly s theorems, k-sets. Rectilinear geometry: intersection and union of rectangles, rectangle searching. Robust geometric computing. Applications of computational geometry.References1.Mark de Berg, Otfried Schwarzkopf, Marc van Kreveld and Mark Overmars, Computational Geometry: Algorithms and Applications, Springer.2.F. P. Preparata and Michael I. Shamos, Computational Geometry: An Introduction, Springer.3.Joseph O Rourke, Computational Geometry in C, Cambridge University Press.4.Lecture Notes by David Mount.