Triangulations: Structures for Algorithms and Applications

Triangulations appear everywhere, from volume computations and meshing to algebra and topology. This book studies the subdivisions and triangulations of polyhedral regions and point sets and presents the first comprehensive treatment of the theory of secondary polytopes and related topics. A central theme of the book is the use of the rich structure of the space of triangulations to solve computational problems (e.g., counting the number of triangulations or finding optimal triangulations with respect to various criteria), and to establish connections to 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. With many examples and exercises, and with nearly five hundred illustrations, the book gently guides readers through the properties of the spaces of triangulations of "structured" (e.g., cubes, cyclic polytopes, lattice polytopes) and "pathological" (e.g., disconnected spaces of triangulations) situations using only elementary principles. The book is designed to serve as a textbook or for self-guided study. Beyond good knowledge of linear algebra, all that is required to use this book is maturity to read and understand proofs.

Features:

-- First comprehensive treatment of the theory of regular triangulations, secondary polytopes and related topics appearing in book form
-- Discusses the geometric structure behind the algorithms and shows new emerging applications
-- Theory discusses high-dimensional situations, an area that is not always covered in computational geometry
-- Step-by-step introduction assuming very little background
-- Hundreds of illustrations, examples, and exercises