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. Pack & Prune: Nice distance problems, linear time approximation algorithm.
  2. Fr├ęchet distance: Exact algorithm, c-packed curves, approximation algorithm.

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