2- Course Aim :-

Visibility problems and triangulation, Line sweep and angle sweep; segment intersection, area, perimeter, diameter, width. Planar Point location; Kirkpatrick's hierarchy, Persistent data structure, Multidimiensional data structures: Segment trees, range trees, orthogonal range searching, Convex hulls and Voronoi diagrams; 2d, 3d hulls, 2d Voronoi diagrams, dynamic maintenance, Duality between hulls and Voronoi diagrams, Duality between lines and points, higher order Voronoi diagrams Arrangements: Construction and bounds, k-sets Zone theorem, Algebraic lower bounds; Linear Decision model, Ben-Or's theorem, Randomized algorithms: Random sampling, Incremental construction, Backward analysis Optimization: Monge matrices, Fixed dimensional linear programming, Prune and Search Parametric search; k-th intersection, k-th nearest neighbour. Recent topics: Instructor's choice.