Handbook of Geometric Constraint Systems Principles

Broadly speaking, a geometric constraint system (GCS) consists of basic geometric objects such as points, lines, or rigid bodies that satisfy some specified geometric relationships such as distances, angles, or incidences. Such systems arise in many prac-tical applications, including computer-aided design, molecular and materials modelling, robotics, sensor networks, and machine learning. This handbook is a wide-ranging reference work on the core principles, methods, and results in GCS research. It makes this topic fully accessible to nonspecialists as well as to experts who work in this area professionally, either as academics or as practitioners in fields such as engineering or robotics. The book is divided into four major parts. The first part (Chapters 2–7) deals with geometric reasoning techniques, with many of the approaches based on algebraic meth-ods. It starts with a discussion of techniques for automated geometry theorem proving. In particular, it introduces the bracket algebra and Grassmann-Cayley algebra in the context of proving theorems in projective and Euclidean geometry. These algebras are also discussed in relation to algebraic conditions (and their geometric interpretations) that make realisations of a GCS special. After a discussion of molecular distance geome-try and algebraic invariants in geometric reasoning, the first part of the book concludes with a description of various triangle-decomposable GCSs and algorithms for solving such systems via recursive decompositions and recombinations, as well as generalisations of this method to non-triangle-decomposable GCSs. The second part (Chapters 8–12) discusses techniques for understanding dependent constraints and certain types of rigidity (such as dimensional or universal rigidity) arising from the structure of the Euclidean distance cone. This is followed by a discussion of the structure of general metric cones. Additional topics include Cayley configuration spaces and constraint varieties of mechanisms. The second part of the book concludes with an introduction to real algebraic geometry for geometric constraints. The third part (Chapters 13–17) is dedicated to geometric results and techniques for analysing the rigidity and flexibility of GCSs, with a particular focus on bar-joint frameworks. It discusses the rigidity of polyhedra in 3-space, the rigidity of tensegrity frameworks (i.e., distance-constrained point configurations with equality and inequality constraints), geometric conditions of rigidity in nongeneric settings, methods and results for analysing global rigidity of generic bar-joint frameworks in general dimension, and transformations between metric spaces that preserve various types of rigidity. Finally, the fourth part of the book (Chapters 18–24) is concerned with methods and results in combinatorial rigidity theory, which looks for polynomial-time deterministic algorithms for testing the rigidity of GCSs that are in generic position. It gives detailed discussions of the generic rigidity and global rigidity of bar-joint frameworks (and related structures) in the Euclidean plane, and of frameworks in general dimension consisting of rigid bodies that are connected by bars or hinges. Moreover, it discusses the rigidity of generic point-line and body-and-cad frameworks, the rigidity of bar-joint frameworks where the underlying metric is governed by a polyhedral norm, and the rigidity of frameworks that are as generic as possible subject to certain symmetry or periodicity constraints. Many proofs in combinatorial rigidity are obtained via recursive graph constructions that preserve generic rigidity or global rigidity, and hence a whole chapter is dedicated to this topic. - Bernd Schulze - Mathematical Reviews Clippings - June 2019