Course

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.

TEXT BOOKS /References

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

3. F.P. Preparata and Michael I. Shamos, Computational Geometry: An Introduction, Springer.
4. Joseph O’ Rourke, Computational Geometry in C, Cambridge University
5. Lecture Notes by David Mount.