Polyhedral and Algebraic Methods in Computational Geometry
Michael Joswig, Thorsten Theobald
Springer
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 Contents

Cover

Polyhedral and Algebraic Methods in Computational Geometry

ISBN 9781447148166 ISBN 9781447148173

Preface

Contents

Introduction and Overview

  1.1 Linear Computational Geometry
  1.2 Non-linear Computational Geometry
  1.3 Applications

Part 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 Remarks

Part 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 Remarks

Part 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 Remarks

Algebraic Structures

Separation Theorems

Algorithms and Complexity

Software

Notation

References

Index