Algorithmic Geometry
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.
- Systematic and coherent treatment
- Practical algorithmic approach
- Illustrated with simple but applicable examples
Reviews & endorsements
"This interesting book about computational geometry is a translation of the well known ^Geometrie Algorithmique^...The translation also contains many more concise proofs, new interesting exercises (for instance about data structures), new explanatory figures, and a more extensive index." Mathematical Reviews
"This text book is a careful introduction to this field. It does not aim for completeness, but concentrates on explaining the fundamental ideas, concepts, and structures: deterministic and randomized algorithms, convex hulls, triangulations, arrangements, Voronoi diagrams." Monatshefte fur Mathematik
"This text book is a careful introduction to this field. It does not aim for completeness, but concentrates on explaining the fundamental ideas, concepts, and structures: deterministic and randomized algorithms, convex hulls, triangulations, arrangements, Voronoi diagrams." Monatshefte fur Mathematik
Product details
- Published: March 1998
- Format: Paperback
- ISBN: 9780521565295
- Length: 544 pages
- Dimensions: 246 × 189 × 28 mm
- Weight: 0.96kg
- Contains: 160 b/w illus. 1 table 182 exercises
- Availability: Available
Table 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.
- Show more
