Algorithmic Geometry

• Preface; Part I. Algorithmic Tools: 1. Notions of complexity; 2. Basic data structures; 3. Deterministic methods used in geometry; 4. Random sampling; 5. Randomized algorithms; 6. Dynamic randomized algorithms; Part II. Convex Hulls: 7. Polytopes; 8. Incremental convex hulls; 9. Convex hulls in 2 and 3 dimensions; 10. Linear programming; Part III. Triangulations: 11. Complexes and triangulations; 12 Triangulations in dimension 2; 13. Triangulations in dimension 3; Part IV. Arrangements: 14. Arrangements of hyperplanes; 15. Arrangements of line segments in the plane; 16. Arrangements of triangles; Part V. Voronoi Diagrams: 17. Euclidean metrics; 18. Non-Euclidean metrics; 19. Diagrams in the plane; References; Notation; Index.

'The book is well written … covers a wealth of material, is copiously illustrated, and has a comprehensive bibliography. Especially in view of its modest price, the book would be a welcome addition to the shelves of anyone interested in algorithmic geometry.' Peter McMullen, Bull. London Mathematical Society