Algorithmic Geometry

Advanced textbook in computational geometry; algorithmic approach.

List of contents

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.

Summary

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.

Product details

• Authors: J. -D Boissonnat, Jean-Daniel Boissonnat, Jean-Daniel Yvinec Boissonnat, Mariette Yvinec
• Assisted by: Herve Bronniman (Translation), Herve Bronnimann (Translation)
• Publisher: Cambridge University Press ELT
• Languages: English
• Product format: Paperback / Softback
• Released: 05.03.1998
• EAN: 9780521565295
• ISBN: 978-0-521-56529-5
• No. of pages: 544
• Subject: Natural sciences, medicine, IT, technology > IT, data processing > General, dictionaries