Algorithmic Geometry

The design and analysis of geometric algorithms has seen remarkable growth in recent years, due to their application in computer vision, graphics, medical imaging, and CAD. Geometric algorithms are built on three pillars: geometric data structures, algorithmic data structuring techniques and results from combinatorial geometry. This comprehensive presents a coherent and systematic treatment of the foundations and gives simple, practical algorithmic solutions to problems. An accessible approach to the subject, Algorithmic Geometry is an ideal guide for instructors or for beginning graduate courses in computational geometry. 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 Pt. I. Algorithmic Tools. Ch. 1. Notions Of Complexity. Ch. 2. Basic Data Structures. Ch. 3. Deterministic Methods Used In Geometry. Ch. 4. Random Sampling. Ch. 5. Randomized Algorithms. Ch. 6. Dynamic Randomized Algorithms -- Pt. Ii. Convex Hulls. Ch. 7. Polytopes. Ch. 8. Incremental Convex Hulls. Ch. 9. Convex Hulls In Two And Three Dimensions. Ch. 10. Linear Programming -- Pt. Iii. Triangulations. Ch. 11. Complexes And Triangulations. Ch. 12. Triangulations In Dimension 2. Ch. 13. Triangulations In Dimension 3 -- Pt. Iv. Arrangements. Ch. 14. Arrangements Of Hyperplanes. Ch. 15. Arrangements Of Line Segments In The Plane. Ch. 16. Arrangements Of Triangles -- Pt. V. Voronoi Diagrams. Ch. 17. Euclidean Metric. Ch. 18. Non-euclidean Metrics. Ch. 19. Diagrams In The Plane. Jean-daniel Boissonnat, Mariette Yvinec ; Translated By Hervé Brönnimann. Includes Bibliographical References (p. 492-507) And Index. The goals of this book are twofold: first to present a coherent and systematic treatment of the foundations; secondly to present algorithmic solutions to problems that are simple to state but which nevertheless are applicable in practical situations. The prerequisites for using the book are few, which will make it ideal for teaching advanced courses in computational geometry. Computational geometry aims at designing the most efficient algorithms to solve geometric problems.