COL 752: Geometric Algorithms (3-0-2) Semester I 2016-2017 Instructor : Sandeep Sen

Lectures:

Teaching Assistant:

• Nikhil Kumar (csz148210@cse.iitd.ac.in )

  Prerequisite: Algorithms and data structures.

  Topics:

  Computational geometry studies the design, analysis, and implementation of algorithms and data structures for geometric problems. These problems arise in a wide range of areas, including CAD/CAM, robotics, computer graphics, molecular biology, GIS, spatial databases, sensor networks, and machine learning. In addition to the tools developed in computer science, the study of geometric algorithms also requires ideas from various mathematical disciplines, e.g., combinatorics, topology, algebra, and differential geometry. This close interaction between various mathematical and practical areas has had a beneficial impact on both basic and applied research in computational geometry.

  The goal of this course is to provide an overview of the techniques developed in computational geometry as well as some of its application areas. The topics covered in the course will include:

  1. Geometric Fundamentals: Models of computation, lower bound techniques, geometric primitives, geometric transforms

  2. Convex hulls: Planar convex hulls, higher dimensional convex hulls, randomized, output-sensitive, and dynamic algorithms, applications of convex hull

  3. Intersection detection: segment intersection, line sweep, map overlay, halfspace intersection, polyhedra intersection

  4. Geometric searching: segment, interval, and priority-search trees, point location, persistent data structure, fractional cascading, range searching, nearest-neighbor searching

  5. Proximity problems: closest pair, Voronoi diagram, Delaunay triangulation and their subgraphs, spanners, well separated pair decomposition

  6. Arrangements: Arrangements of lines and hyperplanes, sweep-line and incremental algorithms, lower envelopes, levels, and zones, applications of arrangements

  7. Triangulations: monotone and simple polygon triangulations, point-set triangulations, optimization criteria, Steiner triangulation, Delaunay refinement

  8. Geometric sampling: random sampling and ε-nets, ε-approximation and discrepancy, cuttings, coresets

  9. Geometric optimization: linear programming, LP-type problems, parametric searching, approximation techniques

  10. Implementation Issues : robust computing, perturbation techniques, floating-point filters, rounding techniques

  Organization:

  Grading will be based on a Midterm (25%), Major (40%) and Assignments (30%) including some group programming assignments. Note that it is a 3-0-2 course.

  Attendence related Scribing and class participation will count for 5%. Note that students having less than 75% attendence will be reported for possible penal action according to the attendence rules of the institute.

  Assignments

  Problem Set 1

  Problem Set 2

  Midterm with solns

  Minor PDF with solns

  Major exam with solns

  A talk on randomized geometric algorithms

  NPTEL Videos of a previous version of this course

  Reference books

  Computational Geometry by M. de Berg, M. van Kreveld, M. Overmars, and O. Schwarzkopf, pub: Springer

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

  Algorithms in Combinatorial Geometry, H. Edelsbrunner, pub: Springer-Verlag (EATCS Monograph)

  Computational Geometry - an introduction, Preparata and Shamos, pub: Springer-Verlag.

  Computational Geometry: an Introduction through randomization, K. Mulmuley, Pub: Prentice Hall.

  LEDA - a platform for combinatorial and geometric computing, Mehlhorn and Naher, pub: Cambridge.

  Lectures (from NPTEL version - not in the same order as the video)

  Lecture 1 (Introduction/Visibility)   Lecture 2 (Art-Gallery problem)   Lecture 3 (Maximal points output-sensitive)   Lectures 4,5 (Plane sweep : segment intersections)

    Lecture 6 (area rectangles/segment tree)   Lectures 7,8 (convex hull)   Lecture 9 (Quickhull)   Lecture 10 (Convex hull cont)

  Lecture 11 (Duality)   Lecture 12 (Dulaity)   Lecture 13 (algebraic tree lower bound)   Lecture 14 (point location)   Lecture 15 (Kirpatrick's refinement)  

  Lecture 16 (Rand Incr Constr)   Lecture 17 (Voronoi Diagrams)   Lecture 18(Voro Diagr using minim)   Lecture 19 (Incr Delaunay triang)   Lecture 19a   Lecture 20 (Backward analysis)  

  Lecture 21 (RIC: general)   Lecture 23 (Arrangements)   Lecture 24 (Zone theorem)   Lecture 25 (Levels)  

  Lecture 26 (Range Search)   Lecture 27 (k-d trees)   Lecture 28 (priority trees)   Lecture 29 (Well-separated decomp)   Lecture 30 (Quadtrees)  

  Lecture 31 (non-ortho Range search)   Lecture 32 (Cuttings)   Lecture 33 (eps WSPD)   Lecture 34 (geometric spanners)   Lecture 35 (eps-nets and VC dimen)  

  Lecture 36 (VC dimen) Lecture 37 (Geometric set cover)   Lecture 38 (cont. )   Lecture 39 (Shape Analysis)   Lecture 40 (Shape comparison)

  ---

  Sandeep Sen
  Last modified: Mon July 2006