Algorithmic Geometry

Rating:
Summary: A great graduate book to complement the textbooks!
Review: If you've read computational geometry textbooks (like the Preparata-Shamos, or the recent and great "Dutch" book by de Berg et al.), and liked the material, here's your chance to delve into the more mathematical and analytical aspect of the topic. This book is not for an undergraduate class, but its thorough yet readable treatment of arrangements or Voronoi diagrams will bring you up to speed for reading technical articles or more elaborate references (like Edelsbrunner's monograph). The scope is wider than Edelsbrunner's, even though fewer or less technical results appear. For instance, there is an analysis of the complexity of the union of triangles in space (based on recent research results).

The book takes the viewpoint of randomized algorithms, which are very simple to describe and implement, and provides general tools for their analysis (on-line or off-line dynamic algorithm). It is based in five parts around geometric structures (polytopes, arrangements, Voronoi diagrams) with two introductory parts (algorithms, randomized analysis -- general theorems).

Many of the algorithms and problems stem from robotics and motion planning. There are many exercises, with either an "algorithmic" interface, or a concrete problem-solving presentation.