IIT Kharagpur

Department of Computer Science and Engineering

Computational Geometry (Spring 2018) Course numbers PG CS60064 (3-0-0) 3 credits.

Moodle course site SPP-CG-2018 Computational Geometry (2018)

First lecture January 04, 2018, CSE 107, 5 pm.

------------ Books and References:

F. P. Preparata and M. I. Shamos, Computational Geometry: An Introduction, New York, NY, Springer-Verlag, 1985.

Herbert Edelsbrunner, Algorithms in Combinatorial Geometry, Springer-Verlag

Subir Kumar Ghosh, Visibility algorithms in the plane, Cambridge University Press, 2007.

Data Structures and Algorithms: Volumes I and III by Kurt Mehlhorn, Springer-Verlag.

Ketan Mulmuley, Computational Geometry: An Introduction through Randomized Algorithms.

Motwani and Raghavan, Randomized Algorithms.

K. Mehlhorn and S. Naher, LEDA: A Platform for Combinatorial and Geometric Computing, Cambridge, UK, Cambridge University Press, 1999.

Mark de Berg, Otfried Schwarzkopf, Marc van Kreveld and Mark Overmars, Computational Geometry: Algorithms and Applications, Springer.

Joseph O' Rourke, Computational Geometry in C, Cambridge University Press.

============================================================================= =============================================================================

CS41102 COMPUTATIONAL GEOMETRY L-T-P: 3-1-0, Credits: 4 [Actual number CS40026 Autumn 2010 ERP]

Introduction: historical perspective, geometric preliminaries. Convex hulls algorithms in 2d and 3d, lower bounds. Triangulations: polygon triangulations, representations, point-set triangulations. Voronoi diagrams: algorithms, closest pair problems. Delaunay 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.

References

1. 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.

=============================================================================

CS60064 COMPUTATIONAL GEOMETRY L-T-P: 3-0-0, Credits: 3

Convex hulls: construction in 2d and 3d, lower bounds; Triangulations: polygon triangulations, representations, point-set triangulations, planar graphs; Voronoi diagrams: construction and applications, variants; Delaunay triangulations: divide-and-conquer, flip and incremental algorithms, duality of Voronoi diagrams, min-max angle properties; Geometric searching: point location, fractional cascading, linear programming with prune and search, finger trees, concatenable queues, segment trees, interval trees; Visibility: algorithms for weak and strong visibility, visibility with reflections, art-gallery problems; Arrangements of lines: arrangements of hyperplanes, zone theorems, many-faces complexity and algorithms; Combinatorial geometry: Ham-sandwich cuts, Helly's theorems, k-sets, polytopes and hierarchies, polytopes and linear programming in d-dimensions, complexity of the union of convex sets, simply connected sets and visible regions; Sweep techniques: plane sweep for segment intersections, Fortune's sweep for Voronoi diagrams, topological sweep for line arrangements; Randomization in computational geometry: algorithms, techniques for counting; Robust geometric computing; Applications of computational geometry.

References

1. 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.