Home | Bookmarks | Papers | Blog |

This is the webpage for the book

- AMS webpage.
- Table of content
- Front stuff - table of content/preface/etc.
**Errata**- An early version of the book from 2008 is available online
here. The final version of the book
is way way better, but unfrotunately I can not make it
available...
(The final version is considerably longer, contain more stuff, contain less typos, etc...)

- The power of grids: Closest pair and smallest enclosing disk.
- Pack & Prune: Nice distance problems, linear time approximation algorithm.
- VC dimensions, eps-net, eps-sample theorems.
- LSH: Contains a simpler LSH construction for the hypercube case than the one presented in the original version of the book.
- Linear programming in low dimensions: Linear time algorithms for LP, LP-type problems, and violator spaces.
- Duality.

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

- Fréchet distance: Exact algorithm, c-packed curves, approximation algorithm.

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