Instructor:  Pankaj K. Agarwal

TA:  Jiangwei Pan

Time:  TuTh 4:40-5:55

Location:  LSRC D243


The field of Geometric Algorithms 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 geometric algorithms as well as some of its application areas. The topics covered in the course will include:

  1. Geometric Fundamentals: Motivation, models of computation, 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, 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
  7. Triangulations: Polygon triangulations, point-set triangulations, Steiner triangulation, Delaunay refinement, mesh simplification
  8. Geometric sampling: Random sampling and e-nets, e-approximation and discrepancy, cuttings, coresets
  9. Geometric optimization: Linear programming, geometric set cover, shape matching
  10. Embeddings: Bourgain's theorem, random-projection, low-distortion embeddings, locality sensitive hashing



The main textbook for this course:
M. de Berg, O. Cheong, M. van Kreveld, and M. Overmars, Computational Geometry: Algorithms and Applications. Springer-Verlag, 3rd ed., 2008.



Assignments: 40% weight
Four assignments will be given during the semester, which each student has to complete individually without searching the material online.

Lecture Scribe: 10% weight
Each student will scribe one lecture.

Research Project: 50% weight
Intended to produce a work of publishable quality, the project should consist of a comprehensive survey on a topic plus new research work. Due on April 25, 2014.