De Loera J.A., Rambau J., Santos F. Triangulations. Structures for Algorithms and Applications

Springer, 2010, -550 p.Triangulations appear in many different parts of mathematics and computer science since they are the natural way to decompose a region of space into smaller, easy-to-handle pieces. From volume computations and meshing to algebra and topology, there are many natural situations in which one has a fixed set of points that can be used as vertices for the triangulation. Typically one wants to find an optimal triangulation of those points or to explore the set of their all triangulations. The given points may represent the sites for a Delaunay triangulation computation, the test points for a surface reconstruction, or a set of monomials, represented as lattice points in Zd, in an algebraicgeometric meaning.
A central theme of this book is to use the rich geometric structure of the space of triangulations of a given set of points to solve computational problems (e.g., counting the number of triangulations or finding optimal triangulations with respect to various criteria), and for setting up connections to novel applications in algebra, computer science, combinatorics, and optimization. Thus at the heart of the book is a comprehensive treatment of the theory of regular subdivisions, secondary polytopes, flips, chambers, and their interactions. Again, we firmly believe that understanding the fundaments of geometry and combinatorics pays up for algorithms and applications. The book is designed to serve as a textbook or for self-guided study. It was written with graduate students or advanced undergraduates as the target audience (in fact, several groups of students were kind enough to let us test the book with them). Beyond good knowledge of linear algebra, all that is required to use this book is maturity to read and understand proofs. With many examples and exercises, and with over five hundred illustrations, we aim to gently introduce beginners to the properties of the spaces of triangulations of highly-structured (e.g., cubes, cyclic polytopes, lattice polytopes, etc.) and pathological situations (e.g., disconnected spaces of triangulations, NP-hardness constructions, etc.). We do this in arbitrary dimension, while using only elementary geometric principles.
We are excited to present many open questions. Some are new, but many have been open for some time. Also, the book contains many new results appearing here for the first time, besides corrections and simpler proofs of well-known theorems.Triangulations in Mathematics
Configurations, Triangulations, Subdivisions, and Flips
Life in Two Dimensions
A Tool Box
Regular Triangulations and Secondary Polytopes
Some Interesting Configurations
Some Interesting Triangulations
Algorithmic Issues
Further Topics