Computational Geometry
R. Inkulu at cse.iitg


Overview      [dB]: 1-2, 10-13

Windowing queries Stabbing queries Intersections Arrangements Planar point location Convex hulls Planar triangulations Voronoi diagrams Duality Closest pair of points Algo for LP in plane      [dB]: 66-82; [PS]: 292-297 Smallest enclosing disk      [dB]: 86-89; [P]: 210-213 Visibility Path planning Power of grids Coreset for directional width      [P]: 291-294 WSPD and its applications      [P]: 29-39 Worst-case lower bounds

* [PS]: Computational Geometry: An Introduction by Franco P. Preparata and Ian Shamos.
* [dB]: Computational Geometry: Algorithms and Applications by Mark de Berg et al., Third Edition.
* [P]: Geometric Approximation Algorithms by Sariel Har-Peled.

* AR stands for additional reading (no lecture delivered).
* OR stands for lecture delivered but not included in exams (hence, optional reading).