دانلود کتاب Polyhedral and Algebraic Methods in Computational Geometry

Polyhedral and Algebraic Methods in Computational Geometry provides a thorough introduction into algorithmic geometry and its applications. It presents its primary topics from the viewpoints of discrete, convex and elementary algebraic geometry. The first part of the book studies classical problems and techniques that refer to polyhedral structures. The authors include a study on algorithms for computing convex hulls as well as the construction of Voronoi diagrams and Delone triangulations. The second part of the book develops the primary concepts of (non-linear) computational algebraic geometry. Here, the book looks at Gröbner bases and solving systems of polynomial equations. The theory is illustrated by applications in computer graphics, curve reconstruction and robotics. Throughout the book, interconnections between computational geometry and other disciplines (such as algebraic geometry, optimization and numerical mathematics) are established. Polyhedral and Algebraic Methods in Computational Geometry is directed towards advanced undergraduates in mathematics and computer science, as well as towards engineering students who are interested in the applications of computational geometry.Table of ContentsCoverPolyhedral and Algebraic Methods in Computational GeometryISBN 9781447148166 ISBN 9781447148173PrefaceContentsIntroduction and Overview 1.1 Linear Computational Geometry 1.2 Non-linear Computational Geometry 1.3 ApplicationsPart I Linear Computational Geometry Geometric Fundamentals 2.1 Projective Spaces 2.2 Projective Transformations 2.3 Convexity o 2.3.1 Orientation of Affin Hyperplanes o 2.3.2 Separation Theorems 2.4 Exercises 2.5 Remarks Polytopes and Polyhedra 3.1 Definition and Fundamental Properties o 3.1.1 The Faces of a Polytope o 3.1.2 First Consequences of the Separating Hyperplane Theorem o 3.1.3 The Outer Description of a Polytope 3.2 The Face Lattice of a Polytope 3.3 Polarity and Duality 3.4 Polyhedra 3.5 The Combinatorics of Polytopes 3.6 Inspection Using polymake o 3.6.1 Cyclic Polytopes o 3.6.2 Random Polytopes o 3.6.3 Projective Transformations 3.7 Exercises 3.8 Remarks Linear Programming 4.1 The Task 4.2 Duality 4.3 The Simplex Algorithm 4.4 Determining a Start Vertex 4.5 Inspection Using polymake 4.6 Exercises 4.7 Remarks Computation of Convex Hulls 5.1 Preliminary Considerations 5.2 The Double Description Method 5.3 Convex Hulls in the Plane 5.4 Inspection Using polymake 5.5 Exercises 5.6 Remarks Voronoi Diagrams 6.1 Voronoi Regions 6.2 Polyhedral Complexes 6.3 Voronoi Diagrams and Convex Hulls 6.4 The Beach Line Algorithm o 6.4.1 The Algorithm 6.5 Determining the Nearest Neighbor 6.6 Exercises 6.7 Remarks Delone Triangulations 7.1 Duality of Voronoi Diagrams 7.2 The Delone Subdivision 7.3 Computation of Volumes 7.4 Optimality of Delone Triangulations 7.5 Planar Delone Triangulations 7.6 Inspection Using polymake 7.7 Exercises 7.8 RemarksPart II Non-linear Computational Geometry Algebraic and Geometric Foundations 8.1 Motivation 8.2 Univariate Polynomials 8.3 Resultants 8.4 Plane Affin Algebraic Curves 8.5 Projective Curves 8.6 B�zout's Theorem 8.7 Algebraic Curves Using Maple 8.8 Exercises 8.9 Remarks Gr�bner Bases and Buchberger's Algorithm 9.1 Ideals and the Univariate Case 9.2 Monomial Orders 9.3 Gr�bner Bases and the Hilbert Basis Theorem 9.4 Buchberger's Algorithm 9.5 Binomial Ideals 9.6 Proving a Simple Geometric Fact Using Gr�bner Bases 9.7 Exercises 9.8 Remarks Solving Systems of Polynomial Equations Using Gr�bner Bases 10.1 Gr�bner Bases Using Maple and Singular 10.2 Elimination of Unknowns 10.3 Continuation of Partial Solutions 10.4 The Nullstellensatz 10.5 Solving Systems of Polynomial Equations 10.6 Gr�bner Bases and Integer Linear Programs 10.7 Exercises 10.8 RemarksPart III Applications Reconstruction of Curves 11.1 Preliminary Considerations 11.2 Medial Axis and Local Feature Size 11.3 Samples and Polygonal Reconstruction 11.4 The Algorithm NN-Crust 11.5 Curve Reconstruction with polymake 11.6 Exercises 11.7 Remarks Pl�cker Coordinates and Lines in Space 12.1 Pl�cker Coordinates 12.2 Exterior Multiplication and Exterior Algebra 12.3 Duality 12.4 Computations with Pl�cker Coordinates 12.5 Lines in R3 o 12.5.1 Transversals 12.6 Exercises 12.7 Remarks Applications of Non-linear Computational Geometry 13.1 Voronoi Diagrams for Line Segments in the Plane 13.2 Kinematic Problems and Motion Planning 13.3 The Global Positioning System GPS 13.4 Exercises 13.5 RemarksAlgebraic StructuresSeparation TheoremsAlgorithms and ComplexitySoftwareNotationReferencesIndex