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.

What not to do

Do not go to b-ok.org and search for "geometric approximation algorithms". If you fail not to do it, you might get a link to a pdf version of the book.

Updated chapters

Here are some chapter(s) I updated.
  1. The power of grids: Closest pair and smallest enclosing disk.
  2. Pack & Prune: Nice distance problems, linear time approximation algorithm.
  3. VC dimensions, eps-net, eps-sample theorems.
  4. LSH: Contains a simpler LSH construction for the hypercube case than the one presented in the original version of the book.
  5. Linear programming in low dimensions: Linear time algorithms for LP, LP-type problems, and violator spaces.
  6. Duality.

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.

New chapters on other topics

  1. Fr├ęchet distance: Exact algorithm, c-packed curves, approximation algorithm.

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