1st Edition

Handbook of Geometric Constraint Systems Principles

Edited By Meera Sitharam, Audrey St. John, Jessica Sidman Copyright 2018
    604 Pages 209 B/W Illustrations
    by Chapman & Hall

    604 Pages 209 B/W Illustrations
    by Chapman & Hall

    The Handbook of Geometric Constraint Systems Principles is an entry point to the currently used principal mathematical and computational tools and techniques of the geometric constraint system (GCS). It functions as a single source containing the core principles and results, accessible to both beginners and experts.

    The handbook provides a guide for students learning basic concepts, as well as experts looking to pinpoint specific results or approaches in the broad landscape. As such, the editors created this handbook to serve as a useful tool for navigating the varied concepts, approaches and results found in GCS research.

    Key Features:

      • A comprehensive reference handbook authored by top researchers
      • Includes fundamentals and techniques from multiple perspectives that span several research communities
      • Provides recent results and a graded program of open problems and conjectures
      • Can be used for senior undergraduate or graduate topics course introduction to the area
      • Detailed list of figures and tables

    About the Editors:

    Meera Sitharam is currently an Associate Professor at the University of Florida’s Department of Computer & Information Science and Engineering. She received her Ph.D. at the University of Wisconsin, Madison.

    Audrey St. John is an Associate Professor of Computer Science at Mount Holyoke College, who received her Ph. D. from UMass Amherst.

    Jessica Sidman is a Professor of Mathematics on the John S. Kennedy Foundation at Mount Holyoke College. She received her Ph.D. from the University of Michigan.

    Overview and preliminaries. Computer-assisted Theorem Proving in Synthetic Geometry. Coordinate-Free Theorem Proving in Incidence Geometry. Special positions of frameworks and the Grassmann-Cayley Algebra. From Molecular Distance Geometry to Conformal Geometric Algebra. Tree-decomposable and Underconstrained Geometric Constraint Problems. Geometric Constraint Decomposition: The General Case. Dimensional and Universal Rigidities of Bar Frameworks. Computations of metric/cut polyhedra and their relatives. Cayley Configuration Spaces. Constraint Varieties in Mechanism Science. Real Algebraic Geometry for Geometric Constraints. Polyhedra in 3-Space. Tensegrity. Geometric Conditions of Rigidity in Nongeneric settings. Generic Global Rigidity in General Dimension. Change of Metrics in Rigidity Theory. Planar Rigidity. Inductive constructions for combinatorial local and global rigidity. Rigidity of Body-bar-hinge Frameworks. Global rigidity of two-dimensional frameworks. Point-line frameworks. Generic rigidity of body-and-cad frameworks. Rigidity with polyhedral norms. Combinatorial rigidity of symmetric and periodic frameworks.

    Biography

    Meera Sitharam is currently an Associate Professor at the University of Florida’s Department of Computer & Information Science and Engineering. She received her Ph.D. at the University of Wisconsin, Madison. http://www.cise.ufl.edu/~sitharam

    Audrey St. John is an Associate Professor of Computer Science at Mount Holyoke College, who received her Ph. D. from UMass Amherst. http://minerva.cs.mtholyoke.edu/

    Jessica Sidman is a Professor of Mathematics on the John S. Kennedy Foundation at Mount Holyoke College. She received her Ph.D. from the University of Michigan. http://www.mtholyoke.edu/~jsidman/

    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