Home Bookmarks Papers Blog

Geometric approximation algorithms

by Sariel Har-Peled.
This is the webpage for the book Geometric approximation algorithms that is published by the AMS.

Additional chapters

Here some addiontal notes/chapters that were written after the book publication. These are all early versions with many many many many many typos, but hopefully they should be helpful to somebody out there (maybe):

Planar graphs

  1. Planar graphs: Basic definitions, Jordan theorem (without proof), straightline embedding, Kuratowski theorem (without proof), planarity testing algorithm.
  2. Grid embedding: Canonical ordering, grid embedding using canonical ordering, breaking a trinagulations into trees (i.e., realizers), grid embedding using realizers.
  3. Circle packing theorem: the game of whac-an-angle, proof.
  4. Planar separator: Separator from circle packing, a linear time separator algorithm, Extensions: Cycle separtor, weights, separating a cluster.

Other stuff

  1. The power of grids: Closest pair and smallest enclosing disk.
  2. Pack & Prune: Nice distance problems, linear time approximation algorithm.
  3. Fr├ęchet distance: Exact algorithm, c-packed curves, approximation algorithm.
  4. Linear programming in low dimensions: Linear time algorithms for LP, LP-type problems, and violator spaces.

Last modified: Tue Apr 1 21:08:25 CDT 2014