Algorithmic Geometry

Advanced textbook in computational geometry; algorithmic approach.

Jean-Daniel Boissonnat (Author), Mariette Yvinec (Author), Herve Bronniman (Translated by)

9780521565295, Cambridge University Press

Paperback, published 5 March 1998

544 pages, 160 b/w illus. 1 table 182 exercises
24.6 x 18.9 x 2.8 cm, 0.96 kg

'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

The design and analysis of geometric algorithms have seen remarkable growth in recent years, due to their application in, for example, computer vision, graphics, medical imaging and CAD. The goals of this book are twofold: first to provide a coherent and systematic treatment of the foundations; secondly to present algorithmic solutions that are amenable to rigorous analysis and are efficient in practical situations. When possible, the algorithms are presented in their most general d-dimensional setting. Specific developments are given for the 2- or 3-dimensional cases when this results in significant improvements. The presentation is confined to Euclidean affine geometry, though the authors indicate whenever the treatment can be extended to curves and surfaces. The prerequisites for using the book are few, which will make it ideal for teaching advanced undergraduate or beginning graduate courses in computational 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.

Subject Areas: Mathematical theory of computation [UYA], Algorithms & data structures [UMB]