Muutke küpsiste eelistusi

Handbook of Geometric Constraint Systems Principles [Kõva köide]

Edited by (Mount Holyoke College, South Hadley, Massachusetts, USA), Edited by (Mount Holyoke College, South Hadley, Massachusetts, USA), Edited by (University of Florida, Gainesville, Florida, USA)
  • Formaat: Hardback, 604 pages, kõrgus x laius: 254x178 mm, kaal: 1254 g, 67 Tables, black and white; 209 Illustrations, black and white
  • Sari: Discrete Mathematics and Its Applications
  • Ilmumisaeg: 25-Jul-2018
  • Kirjastus: Chapman & Hall/CRC
  • ISBN-10: 1498738915
  • ISBN-13: 9781498738910
Teised raamatud teemal:
Handbook of Geometric Constraint Systems PrinciplesSuurem pilt
  • Formaat: Hardback, 604 pages, kõrgus x laius: 254x178 mm, kaal: 1254 g, 67 Tables, black and white; 209 Illustrations, black and white
  • Sari: Discrete Mathematics and Its Applications
  • Ilmumisaeg: 25-Jul-2018
  • Kirjastus: Chapman & Hall/CRC
  • ISBN-10: 1498738915
  • ISBN-13: 9781498738910
Teised raamatud teemal:
Püsilink: https://www.kriso.ee/db/9781498738910.html
Märksõnad:
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 Floridas 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.

Arvustused

Broadly speaking, a geometric constraint system (GCS) consists of basic geometric objects such as points, lines, or rigid bodies that satisfy some specied 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 elds such as engineering or robotics.

The book is divided into four major parts. The rst part (Chapters 27) 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 rst 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 812) 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 conguration 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 1317) is dedicated to geometric results and techniques for analysing the rigidity and exibility 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 congurations 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 1824) 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

Foreword xxi
Preface xxiii
Contributors xxv
1 Overview and Preliminaries 1(18)
Meera Sitharam
Troy Baker
1.1 Introduction
2(1)
1.1.1 Specifying a GCS
2(1)
1.1.2 Fundamental GCS Questions
3(1)
1.1.3 Tractability and Computational Complexity
3(1)
1.2 Parts and
Chapters of the Handbook
3(7)
1.2.1 Part I: Geometric Reasoning Techniques
4(1)
1.2.2 Part II: Distance Geometry, Configuration Space, and Real Algebraic Geometry Techniques
5(1)
1.2.3 Part III: Geometric Rigidity Techniques
6(1)
1.2.4 Part IV: Combinatorial Rigidity Techniques
7(2)
1.2.4.1 Inductive Constructions
8(1)
1.2.4.2 Body Frameworks
8(1)
1.2.4.3 Body-Cad, and Point-Line Frameworks
9(1)
1.2.4.4 Symmetric and Periodic Frameworks and Frameworks under Polyhedral Norms
9(1)
1.2.5 Missing Topics and
Chapters
9(1)
1.3 Terminology Reconciliation and Basic Concepts
10(5)
1.3.1 Constrainedness
10(1)
1.3.2 Rigidity of Frameworks
10(2)
1.3.3 Generic Rigidity of Frameworks
12(1)
1.3.4 Approximate Degree-of-Freedom and Sparsity
13(2)
1.4 Alternative Pathway through the Book
15(4)
I Geometric Reasoning, Factorization and Decomposition 19(180)
2 Computer-Assisted Theorem Proving in Synthetic Geometry
21(40)
Julien Narboux
Predrag Janicic
Jacques Fleuriot
2.1 Introduction
22(1)
2.2 Automated Theorem Proving
22(12)
2.2.1 Foundations
23(1)
2.2.2 Nondegenerate Conditions
23(1)
2.2.3 Purely Synthetic Methods
23(1)
2.2.3.1 Early Systems
24(1)
2.2.3.2 Deductive Database Method, GRAMY, and iGeoTutor
24(1)
2.2.3.3 Logic-Based Approaches
26(2)
2.2.4 Semisynthetic Methods
28(1)
2.2.4.1 Area Method
28(1)
2.2.4.2 Full-Angle Method .
30(1)
2.2.4.3 Vector-Based Method
31(1)
2.2.4.4 Mass-Point Method
32(1)
2.2.5 Provers Implementations and Repositories of Theorems
33(1)
2.3 Interactive Theorem Proving
34(28)
2.3.1 Formalization of Foundations of Geometry
34(1)
2.3.1.1 Hilbert's Geometry
35(1)
2.3.1.2 Tarski's Geometry
37(1)
2.3.1.3 Axiom Systems and Continuity Properties
38(1)
2.3.1.4 Other Axiom Systems and Geometries
40(1)
2.3.1.5 Meta-Theory
41(1)
2.3.2 Higher Level Results
41(1)
2.3.3 Other Formalizations Related to Geometry
42(2)
2.3.4 Verified Automated Reasoning
44(17)
3 Coordinate-Free Theorem Proving in Incidence Geometry
61(24)
Jurgen Richter-Gebert
Hongbo Li
3.1 Incidence Geometry
62(5)
3.1.1 Incidence Geometry in the Plane
62(3)
3.1.2 Other Primitive Operations
65(1)
3.1.3 Projective Invariance
66(1)
3.2 Bracket Algebra: Straightening, Division, and Final Polynomials
67(6)
3.2.1 Bracket Algebra and Straightening
67(3)
3.2.2 Division
70(1)
3.2.3 Final Polynomials
71(2)
3.3 Cayley Expansion and Factorization
73(6)
3.3.1 Cayley Expansion
73(2)
3.3.2 Cayley Factorization
75(1)
3.3.3 Cayley Expansion and Factorization in Geometric Theorem Proving
76(1)
3.3.4 Rational Invariants and Antisymmetrization
77(2)
3.4 Bracket Algebra for Euclidean Geometry
79(6)
3.4.1 The Points I and J
79(1)
3.4.2 Proving Euclidean Theorems
80(5)
4 Special Positions of Frameworks and the Grassmann-Cayley Algebra
85(22)
Jessica Sidman
William Traves
4.1 Introduction: the Grassmann-Cayley Algebra and Frameworks
85(2)
4.2 Projective Space
87(4)
4.2.1 Motivation
87(1)
4.2.2 Homogeneous Coordinates and Points at Infinity
88(1)
4.2.3 Equations on Projective Space
88(1)
4.2.4 Duality Between Lines and Points in P2
89(1)
4.2.5 Grassmannians and Plficker Coordinates
89(1)
4.2.6 More About Lines in 3-space
90(1)
4.3 The Bracket Algebra and Rings of Invariants
91(6)
4.3.1 Group Actions and Invariant Polynomials
93(1)
4.3.2 Relations Among the Brackets
94(3)
4.4 The Grassmann-Cayley Algebra
97(3)
4.4.1 Motivation
97(1)
4.4.2 The cross product as a Join
98(1)
4.4.3 Properties of the Exterior Product
99(1)
4.4.4 Brackets and the Grassmann-Cayley algebra
99(1)
4.4.5 The Join and Meet
100(1)
4.5 Cayley Factorization
100(7)
4.5.1 Motivation
100(1)
4.5.2 The Pure Condition as a Bracket Monomial
101(2)
4.5.3 White's Algorithm for Multilinear Grassmann-Cayley Factorization
103(4)
5 From Molecular Distance Geometry to Conformal Geometric Algebra
107(32)
Timothy F. Havel
Hongbo Li
5.1 Euclidean Distance Geometry
107(3)
5.2 The Distance Geometry Theory of Molecular Conformation
110(5)
5.3 Inductive Geometric Reasoning by Random Sampling
115(7)
5.4 From Distances to Advanced Euclidean Invariants
122(7)
5.5 Geometric Reasoning in Euclidean Conformal Geometry
129(10)
6 Tree-Decomposable and Underconstrained Geometric Constraint Problems
139(42)
Ioannis Fudos
Christoph M. Hoffmann
Robert Joan-Arinyo
6.1 Introduction, Concepts, and Scope
140(7)
6.1.1 Geometric Constraint Systems (GCS)
141(1)
6.1.2 Constraint Graph, Deficit, and Generic Solvability
142(2)
6.1.3 Instance Solvability
144(1)
6.1.4 Root Identification and Valid Parameter Ranges
144(1)
6.1.5 Variational and Serializable Constraint Problems
145(1)
6.1.6 Triangle-Decomposing Solvers
145(2)
6.1.7 Scope and Organization
147(1)
6.2 Geometric Constraint Systems
147(1)
6.3 Constraint Graph
148(10)
6.3.1 Geometric Elements and Degrees of Freedom
149(1)
6.3.2 Geometric Constraints
150(1)
6.3.3 Compound Geometric Elements
150(1)
6.3.4 Serializable Graphs
151(2)
6.3.5 Variational Graphs
153(1)
6.3.6 Triangle Decomposability
153(2)
6.3.7 Generic Solvability and the Church-Rosser Property
155(2)
6.3.8 2D and 3D Graphs
157(1)
6.4 Solver
158(10)
6.4.1 2D Triangle-Decomposable Constraint Problems
159(1)
6.4.2 Root Identification and Order Type
160(6)
6.4.3 Extended Geometric Vocabulary
166(2)
6.5 Spatial Geometric Constraints
168(3)
6.6 Under-Constrained Geometric Constraint Problems
171(10)
7 Geometric Constraint Decomposition: The General Case
181(18)
Troy Baker
Meera Sitharam
Rahul Prabhu
7.1 Introduction
181(10)
7.1.1 Terminology and Basic Concepts
182(2)
7.1.2 Triangle-Decomposition
184(1)
7.1.3 Dulmage-Mendelsohn Decomposition
185(1)
7.1.4 Assur Decomposition
186(1)
7.1.5 The Frontier Vertex Algorithm
187(1)
7.1.6 Canonical Decomposition
188(3)
7.2 Efficient Realization
191(4)
7.2.1 Numerical Instability of Rigid Body Incidence and Seam Matroid
191(1)
7.2.2 Optimal Parameterization in Recombination
192(2)
7.2.3 Reconciling Conflicting Combinatorial Preprocessors
194(1)
7.3 Handling Under-and Over-Constrained Systems
195(1)
7.4 User Intervention in DR-Planning
195(2)
7.4.1 Root Selection and Navigation
195(1)
7.4.2 Changing Constraint Parameters
196(1)
7.4.3 Dynamic Maintenance
196(1)
7.5 Conclusion
197(2)
II Distance Geometry, Real Algebraic Geometry, and Configuration Spaces 199(88)
8 Dimensional and Universal Rigidities of Bar Frameworks
201(12)
A.Y. Alfakih
8.1 Introduction
201(1)
8.2 Stress Matrices and Gale Matrices
202(2)
8.3 Dimensional Rigidity Results
204(2)
8.4 Universal Rigidity
206(3)
8.4.1 Affine Motions
206(1)
8.4.2 Universal Rigidity Basic Results
207(1)
8.4.3 Universal Rigidity for Special Graphs
208(1)
8.5 Glossary
209(4)
9 Computations of Metric/Cut Polyhedra and Their Relatives
213(20)
Mathieu Dutour Sikiric
Michel-Marie Deza
Elena I. Deza
9.1 Introduction
213(2)
9.2 Metric and Cut Cones and Polytopes
215(1)
9.3 Hypermetric Cone and Hypermetric Polytope
216(2)
9.4 Cut and Metric Polytopes of Graphs
218(4)
9.5 Quasi-Semimetric Polyhedra
222(2)
9.6 Partial Metrics
224(1)
9.7 Supermetric and Hemimetric Cones
225(3)
9.8 Software Computations
228(5)
10 Cayley Configuration Spaces
233(20)
Meera Sitharam
Menghan Wang
Joel Willoughby
Rahul Prabhu
10.1 Introduction
233(2)
10.1.1 Euclidean Distance Cone
234(1)
10.2 Glossary
235(1)
10.3 Related
Chapters
235(1)
10.4 Characterizing 2D Graphs with Convex Cayley Configuration Spaces
236(2)
10.5 Extension to other Norms, Higher Dimensions, and Flattenability
238(7)
10.5.1 Computing Bounds of Convex Cayley Configuration Spaces in 3D for Partial 3-Trees
240(1)
10.5.2 Some Background on the Distance Cone
240(2)
10.5.3 Genericity and Independence in the Context of Flattenability
242(3)
10.6 Efficient Realization through Optimal Cayley Modification
245(1)
10.7 Cayley Configuration Spaces of 1-Dof Tree-Decomposable Linkages in 2D
246(4)
10.8 Conclusion
250(3)
11 Constraint Varieties in Mechanism Science
253(20)
Hans-Peter Schrocker
Martin Pfurner
Josef Schadlbauer
11.1 Introduction
253(2)
11.1.1 Linkages and Joints
254(1)
11.1.2 Base and End-Effector Frame
255(1)
11.2 Mechanisms and Algebraic Varieties
255(7)
11.2.1 Geometric Constraint Equations
256(1)
11.2.2 Study Parameters
256(2)
11.2.3 Dual Quaternions
258(2)
11.2.4 Analyzing Mechanisms via Algebraic Varieties
260(2)
11.3 Serial Manipulators
262(4)
11.3.1 Direct and Inverse Kinematics
264(1)
11.3.2 Synthesis of Open and Closed Serial Chains
264(2)
11.3.3 Singularities and Path Planning
266(1)
11.3.4 Open Problems
266(1)
11.4 Parallel Manipulators
266(7)
11.4.1 Direct and Inverse Kinematics
267(1)
11.4.2 Singularities and Self-Motions
268(1)
11.4.3 Open Problems
269(4)
12 Real Algebraic Geometry for Geometric Constraints
273(14)
Frank Sottile
12.1 Introduction
273(2)
12.2 Ideals and Varieties
275(1)
12.3 ...and Algorithms
276(1)
12.4 Structure of Algebraic Varieties
277(3)
12.4.1 Zariski Topology
278(1)
12.4.2 Smooth and Singular Points
279(1)
12.4.3 Maps
279(1)
12.5 Real Algebraic Geometry
280(9)
12.5.1 Algebraic Relaxation
280(1)
12.5.2 Semi-Algebraic Sets
281(2)
12.5.3 Certificates
283(4)
III Geometric Rigidty 287(88)
13 Polyhedra in 3-Space
289(10)
Brigitte Servatius
13.1 Euler's Conjecture
289(1)
13.2 Cauchy's Theorem
289(1)
13.3 Co-Dimension 2 Results-Bricard Octahedra
290(2)
13.4 Polyhedral Surfaces
292(7)
14 Tensegrity
299(18)
Robert Connelly
Anthony Nixon
14.1 Introduction
299(1)
14.2 Ten segrity Frameworks
300(5)
14.2.1 Combinatorics of Tensegrities
304(1)
14.2.2 Geometric Interpretations
304(1)
14.2.3 Packings
304(1)
14.3 Types of Rigidity
305(4)
14.3.1 Global Rigidity and Stress Matrices
306(1)
14.3.2 Universal and Dimensional Rigidity
306(2)
14.3.3 Operations on Tensegrities
308(1)
14.4 Examples and Applications
309(9)
14.4.1 Examples
310(1)
14.4.2 Applications
311(6)
15 Geometric Conditions of Rigidity in Nongeneric Settings
317(24)
Oleg Karpenkov
15.1 Introduction
318(1)
15.2 Configuration Space of Tensegrities and its Stratification
319(3)
15.2.1 Background
320(1)
15.2.2 Definition of a Tensegrity
320(1)
15.2.3 Stratification of the Space of Tensegrities
321(1)
15.2.4 Tensegrities on 4 Points in the Plane
321(1)
15.3 Extended Cayley Algebra and the Corresponding Geometric Relations
322(3)
15.3.1 Extended Cayley Algebra
322(2)
15.3.2 Geometric Relations on Configuration Spaces of Points and Lines
324(1)
15.4 Geometric Conditions of Infinitesimal Flexibility in Terms of Extended Cayley Algebra
325(3)
15.4.1 Examples in the Plane
325(1)
15.4.2 Frameworks in General Position
326(1)
15.4.3 Non-parallelizable Tensegrities
326(1)
15.4.4 Geometric Conditions for Existence Non-parallelizable Tensegrities
327(1)
15.4.5 Conjecture on Strong Geometric Conditions for Tensegrities
327(1)
15.5 Surgeries on Graphs
328(2)
15.6 Algorithm to Write Geometric Conditions of Realizability of Generic Tensegrities
330(11)
15.6.1 Framed Cycles in General Gosition
330(1)
15.6.1.1 Basic Definitions
330(1)
15.6.1.2 Geometric Conditions for Framed Cycles
331(1)
15.6.1.3 Geometric Conditions for Trivalent Graphs
332(1)
15.6.2 Resolution Schemes
332(1)
15.6.2.1 Definition of Resolution Schemes
332(1)
15.6.2.2 Resolution of a Framework
333(1)
15.6.2.3 Hc13-Surgeries on Completely Generic Resolution Schemes
333(2)
15.6.3 Construction of Framing for Pairs of Leaves in Completely Generic Resolution Schemes
335(1)
15.6.4 Framed Cycles Associated to Generic Resolutions of a Graph
335(1)
15.6.5 Natural Correspondences Between EG(P) and the Set of all Resolutions for G(P)
336(1)
15.6.6 Techniques to Construct Geometric Conditions Defining Tensegrities
336(5)
16 Generic Global Rigidity in General Dimension
341(10)
Steven J. Gortler
16.1 Basic Setup
341(2)
16.2 Connelly's Sufficiency Theorem
343(2)
16.3 Hendrickson's Necessary Conditions
345(2)
16.3.1 Nonsufficiency
346(1)
16.4 Necessity of Connelly's Condition
347(1)
16.5 Randomized Algorithm for Testing Generic Global Rigidity
347(1)
16.6 Surgery
348(1)
16.7 Other Spaces
349(2)
17 Change of Metrics in Rigidity Theory
351(24)
Anthony Nixon
Walter Whiteley
17.1 Introduction
351(1)
17.2 Projective Transfer of Infinitesimal Rigidity
352(9)
17.2.1 Coning and Spherical Frameworks
353(2)
17.2.2 Rigidity Matrices
355(1)
17.2.2.1 Spherical to Affine Transfer
357(1)
17.2.3 Equilibrium Stresses
358(1)
17.2.4 Point-Hyperplane Frameworks
359(1)
17.2.5 Tensegrity Frameworks
360(1)
17.3 Projective Frameworks
361(2)
17.4 Pseudo-Euclidean Geometries
363(1)
17.4.1 Hyperbolic and Minkowski Spaces
364(1)
17.5 Transfer of Symmetric Infinitesimal Rigidity
364(2)
17.5.1 Symmetric Frameworks
365(1)
17.6 Global Rigidity
366(4)
17.6.1 Universal Rigidity
368(1)
17.6.2 Projective Transformations
369(1)
17.6.3 Pseudo-Euclidean Metrics
370(1)
17.7 Summary and Related Topics
370(5)
IV Combinatorial Rigidity 375(192)
18 Planar Rigidity
377(36)
Brigitte Servatius
Herman Servatius
18.1 Rigidity of Bar and Joint Frameworks
378(8)
18.1.1 Rigidity Matrix and Augmented Rigidity Matrices
380(2)
18.1.2 Rigidity Matrix as a Transformation
382(2)
18.1.3 The Infinitesimal Rigidity Matroid of a Framework
384(2)
18.2 Abstract Rigidity Matroids
386(9)
18.2.1 Characterizations of A2 and (A2)1
387(2)
18.2.2 The 2-Dimensional Generic Rigidity Matroid
389(1)
18.2.3 Cycles in g2 (n)
390(1)
18.2.4 Rigid Components of g2(G)
391(2)
18.2.5 Representability of g2 (n)
393(2)
18.3 Rigidity and Connectivity
395(18)
18.3.1 Birigidity
396(1)
18.3.2 Tree Decomposition Theorems
397(1)
18.3.2.1 Computation of Independence in g2 (n)
398(2)
18.3.3 Pinned Frameworks and Assur Decomposition
400(1)
18.3.3.1 Isostatic Pinned Framework
400(6)
18.3.4 Body and Pin Structures
406(1)
18.3.5 Rigidity of Random Graphs
407(6)
19 Inductive Constructions for Combinatorial Local and Global Rigidity
413(22)
Anthony Nixon
Elissa Ross
19.1 Introduction
413(1)
19.2 Rigidity in Pad
414(8)
19.2.1 Inductive Operations on Frameworks
416(2)
19.2.2 Recursive Characterizations of Graphs
418(3)
19.2.3 Combinatorial Characterizations of Rigidity
421(1)
19.3 Body-Bar, Body-Hinge, Molecular, etc.
422(2)
19.3.1 Geometry and Combinatorics
423(1)
19.3.2 Characterizations
424(1)
19.4 Further Rigidity Contexts
424(5)
19.4.1 Frameworks with Symmetry
425(1)
19.4.2 Infinite Frameworks
425(1)
19.4.3 Surfaces
426(2)
19.4.4 Mechanisms
428(1)
19.4.5 Applications of Rigidity Techniques
428(1)
19.4.6 Direction-Length Frameworks and CAD
428(1)
19.4.7 Nearly Generic Frameworks
428(1)
19.5 Summary Tables
429(6)
20 Rigidity of Body-Bar-Hinge Frameworks
435(26)
Csaba Kiraly
Shin-ichi Tanigawa
20.1 Rigidity of Body-Bar-Hinge Frameworks
436(7)
20.1.1 Body-Bar Frameworks
436(4)
20.1.2 Body-Hinge Frameworks
440(2)
20.1.3 Body-Bar-Hinge Frameworks
442(1)
20.2 Generic Rigidity
443(1)
20.2.1 Body-Bar Frameworks
443(1)
20.2.2 Body-Hinge Frameworks
443(1)
20.3 Other Related Models
444(6)
20.3.1 Plate-Bar Frameworks
445(1)
20.3.2 Identified Body-Hinge Frameworks
445(1)
20.3.3 Panel-Hinge Frameworks
446(1)
20.3.4 Molecular Frameworks
446(2)
20.3.5 Body-Pin Frameworks
448(1)
20.3.6 Body-Bar Frameworks with Boundaries
449(1)
20.3.7 Other Variants
450(1)
20.4 Generic Global Rigidity
450(2)
20.4.1 Body-Bar Frameworks
450(1)
20.4.2 Body-Hinge Frameworks
451(1)
20.4.3 Counterexamples to Hendrickson's Conjecture
452(1)
20.5 Graph Theoretical Aspects
452(10)
20.5.1 Tree Packing and Connectivity
453(2)
20.5.2 Brick Partitions
455(1)
20.5.3 Constructive Characterizations
455(1)
20.5.4 Algorithms
455(6)
21 Global Rigidity of Two-Dimensional Frameworks
461(26)
Bill Jackson
Tibor Jordan
Shin-Ichi Tanigawa
21.1 Introduction
462(1)
21.2 Conditions for Global Rigidity
463(1)
21.2.1 Stress Matrix Characterization in Rd
463(1)
21.2.2 Hendrickson's Necessary Conditions for Global Rigidity
464(1)
21.3 Graph Operations
464(2)
21.4 Characterization of Global Rigidity in RI and R2
466(1)
21.5 The Rigidity Matroid
467(3)
21.5.1 Rd-Independent Graphs
468(1)
21.5.2 Rd-Circuits
468(1)
21.5.3 Rd-Connected Graphs
468(2)
21.6 Special Families of Graphs
470(4)
21.6.1 Highly Connected Graphs
470(1)
21.6.2 Vertex-Redundantly Rigid Graphs
471(1)
21.6.3 Vertex Transitive Graphs
471(1)
21.6.4 Graphs of Large Minimum Degree
472(1)
21.6.5 Random Graphs
472(1)
21.6.6 Unit Disk Graphs
473(1)
21.6.7 Squares of Gaphs, Line Graphs, and Zeolites
473(1)
21.7 Related Properties
474(5)
21.7.1 Globally Linked Pairs of Vertices
474(2)
21.7.2 Globally Rigid Clusters
476(1)
21.7.3 Globally Loose Pairs
476(1)
21.7.4 Uniquely Localizable Vertices
477(1)
21.7.5 The Number of Non-Equivalent Realizations
477(1)
21.7.6 Stability Lemma and Neighborhood Results
478(1)
21.8 Direction Constraints
479(3)
21.8.1 Parallel Drawings
480(1)
21.8.2 Direction-Length Global Rigidity
481(1)
21.9 Algorithms
482(1)
21.10 Optimization Problems
482(5)
22 Point-Line Frameworks
487(18)
Bill Jackson
J.C. Owen
22.1 Introduction
487(3)
22.1.1 Motivation from CAD
488(1)
22.1.2 Motivation from Automated Deduction in Geometry (ADG) and Theorem Proving
488(1)
22.1.3 Constraint Graphs and Frameworks
488(2)
22.2 Point-Line Graphs and Frameworks
490(6)
22.2.1 Point-Line Frameworks and the Rigidity Map
491(1)
22.2.2 The Rigidity Matrix
492(2)
22.2.3 The Rigidity Matroid
494(1)
22.2.4 Affine Properties of the Point-Line Rigidity Matrix
494(1)
22.2.5 Fixed-Slope Point-Line Frameworks
495(1)
22.3 Characterization of the Generic Rigidity Matroid for Point-Line Frameworks in R2
496(6)
22.3.1 A Count Matroid for Point-Line Graphs
496(3)
22.3.2 A Characterization of Independence in MPL(G) when G is Naturally Bi- partite
499(2)
22.3.3 A Characterization of Independence in MPL(G)
501(1)
22.3.4 The Rank Function for MPL(G)
501(1)
22.4 Extensions to Rd
502(1)
22.4.1 Point-Line Frameworks in Rd
502(1)
22.4.2 Point-Hyperplane Frameworks in Rd
502(1)
22.5 Direction-Length Frameworks
503(2)
23 Generic Rigidity of Body-and-Cad Frameworks
505(20)
Audrey St. John
23.1 Overview
505(1)
23.2 Algebraic Body-and-Cad Rigidity Theory
506(7)
23.2.1 Glossary
506(1)
23.2.2 Getting to Know Body-and-Cad Frameworks
507(2)
23.2.3 Formalization of the Algebraic Setting
509(3)
23.2.4 Building a 3D Body-and-Cad Framework
512(1)
23.3 Infinitesimal Body-and-Cad Rigidity Theory
513(4)
23.3.1 Glossary
513(2)
23.3.2 The Pattern of the Rigidity Matrix
515(1)
23.3.2.1 Primitive Angular and Blind Constraints
515(2)
23.3.3 Generic Rigidty
517(1)
23.4 Combinatorial Body-and-Cad Rigidity Theory
517(5)
23.4.1 Glossary
517(1)
23.4.2 The Rigidity Matroid and Sparsity
518(1)
23.4.3 Characterizing Generic Body-and-Cad Rigidity
518(1)
23.4.4 Algorithms
519(3)
23.5 Open Questions
522(3)
24 Rigidity with Polyhedral Norms
525(18)
Derek Kitson
24.1 Introduction
525(2)
24.1.1 Glossary
526(1)
24.1.2 Statement of the Problem
527(1)
24.2 Rigidity of Frameworks
527(8)
24.2.1 Points of Differentiability
527(1)
24.2.2 The Rigidity Matrix
528(1)
24.2.3 Framework Colors
529(1)
24.2.4 Connectivity
530(1)
24.2.5 Path Chasing
530(1)
24.2.6 Symmetry
531(4)
24.3 Rigidity of Graphs
535(8)
24.3.1 Sparsity Counts and Tree Decompositions
536(1)
24.3.2 Regular Points
536(1)
24.3.3 Symmetric Isostatic Placements
537(2)
24.3.4 Symmetric Tree Decompositions
539(4)
25 Combinatorial Rigidity of Symmetric and Periodic Frameworks
543(24)
Bernd Schulze
25.1 Introduction
543(1)
25.2 Incidentally Symmetric Isostatic Frameworks
544(5)
25.2.1 Glossary
544(1)
25.2.2 Symmetry-Adapted Maxwell Counts
545(3)
25.2.3 Characterizations of Symmetric Isostatic Graphs
548(1)
25.3 Forced-Symmetric Frameworks
549(5)
25.3.1 Glossary
549(2)
25.3.2 Symmetric Motions and the Orbit Rigidity Matrix
551(2)
25.3.3 Characterizations of Forced-Symmetric Rigid Graphs
553(1)
25.4 Incidentally Symmetric Infinitesimally Rigid Frameworks
554(5)
25.4.1 Glossary
554(2)
25.4.2 Phase-Symmetric Orbit Rigidity Matrices
556(1)
25.4.3 Characterizations of Symmetric Infinitesimally Rigid Graphs
557(2)
25.5 Periodic Frameworks
559(8)
25.5.1 Glossary
559(1)
25.5.2 Maxwell Counts for Periodic Rigidity
560(1)
25.5.3 Characterizations of Periodic Rigid Graphs
561(6)
Index 567
Meera Sitharam is currently an Associate Professor at the University of Floridas 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/