Handbook of geometric constraint systems principles

Cover......Page 1
Half title......Page 2
Series Editors......Page 3
Title......Page 4
Copyrights......Page 5
Dedication......Page 6
Contents......Page 10
Foreword......Page 22
Preface......Page 24
Contributors......Page 26
Chapter 1 Overview and Preliminaries Meera Sitharam and Troy Baker......Page 28
  1.1.1 Specifying a GCS......Page 29
 1.2 Parts and Chapters of the Handbook......Page 30
  1.2.1 Part I: Geometric Reasoning Techniques......Page 31
  1.2.2 Part II: Distance Geometry, Configuration Space, and Real Algebraic Ge-ometry Techniques......Page 32
  1.2.3 Part III: Geometric Rigidity Techniques......Page 33
  1.2.4 Part IV: Combinatorial Rigidity Techniques......Page 34
   1.2.4.2 Body Frameworks......Page 35
  1.2.5 Missing Topics and Chapters......Page 36
  1.3.2 Rigidity of Frameworks......Page 37
  1.3.3 Generic Rigidity of Frameworks......Page 39
  1.3.4 Approximate Degree-of-Freedom and Sparsity......Page 40
 1.4 Alternative Pathway through the Book......Page 42
Part I Geometric Reasoning, Factorization and Decomposition......Page 46
Chapter2 Computer-Assisted Theorem Proving in Synthetic Geometry Julien Narboux, Predrag Janici´c, and Jacques Fleuriot......Page 48
 2.2 Automated Theorem Proving......Page 49
  2.2.3 Purely Synthetic Methods......Page 50
   2.2.3.2 Deductive Database Method, GRAMY, and iGeoTutor......Page 51
   2.2.3.3 Logic-Based Approaches......Page 53
   2.2.4.1 Area Method......Page 55
   2.2.4.2 Full-Angle Method......Page 57
   2.2.4.3 Vector-Based Method......Page 58
   2.2.4.4 Mass-Point Method......Page 59
  2.2.5 Provers Implementations and Repositories of Theorems......Page 60
  2.3.1 Formalization of Foundations of Geometry......Page 61
   2.3.1.1 Hilbert’s Geometry......Page 62
   2.3.1.2 Tarski’s Geometry......Page 64
   2.3.1.3 Axiom Systems and Continuity Properties......Page 65
   2.3.1.4 Other Axiom Systems and Geometries......Page 67
  2.3.2 Higher Level Results......Page 68
  2.3.3 Other Formalizations Related to Geometry......Page 69
  2.3.4 Verified Automated Reasoning......Page 71
Chapter3 Coordinate-Free Theorem Proving in Incidence Geometry J¨urgen Richter-Gebert and Hongbo Li......Page 88
  3.1.1 Incidence Geometry in the Plane......Page 89
  3.1.2 Other Primitive Operations......Page 92
  3.1.3 Projective Invariance......Page 93
  3.2.1 Bracket Algebra and Straightening......Page 94
  3.2.2 Division......Page 97
  3.2.3 Final Polynomials......Page 98
  3.3.1 Cayley Expansion......Page 100
  3.3.2 Cayley Factorization......Page 102
  3.3.3 Cayley Expansion and Factorization in Geometric Theorem Proving......Page 103
  3.3.4 Rational Invariants and Antisymmetrization......Page 104
  3.4.1 The Points I and J......Page 106
  3.4.2 Proving Euclidean Theorems......Page 107
 4.1 Introduction: the Grassmann-Cayley Algebra and Frameworks......Page 112
  4.2.1 Motivation......Page 114
  4.2.3 Equations on Projective Space......Page 115
  4.2.5 Grassmannians and Pl¨ucker Coordinates......Page 116
  4.2.6 More About Lines in 3-space......Page 117
 4.3 The Bracket Algebra and Rings of Invariants......Page 118
  4.3.1 Group Actions and Invariant Polynomials......Page 120
  4.3.2 Relations Among the Brackets......Page 121
  4.4.1 Motivation......Page 124
  4.4.2 The cross product as a Join......Page 125
  4.4.4 Brackets and the Grassmann-Cayley algebra......Page 126
  4.5.1 Motivation......Page 127
  4.5.2 The Pure Condition as a Bracket Monomial......Page 128
  4.5.3 White’s Algorithm for Multilinear Grassmann-Cayley Factorization......Page 130
 5.1 Euclidean Distance Geometry......Page 134
 5.2 The Distance Geometry Theory of Molecular Conformation......Page 137
 5.3 Inductive Geometric Reasoning by Random Sampling......Page 142
 5.4 From Distances to Advanced Euclidean Invariants......Page 149
 5.5 Geometric Reasoning in Euclidean Conformal Geometry......Page 156
Chapter6 Tree-Decomposable and Underconstrained Geometric Constraint Problems Ioannis Fudos, Christoph M. Hoffmann, and Robert Joan-Arinyo......Page 166
 6.1 Introduction, Concepts, and Scope......Page 167
  6.1.1 Geometric Constraint Systems (GCS)......Page 168
  6.1.2 Constraint Graph, Deficit, and Generic Solvability......Page 169
  6.1.4 Root Identification and Valid Parameter Ranges......Page 171
  6.1.6 Triangle-Decomposing Solvers......Page 172
 6.2 Geometric Constraint Systems......Page 174
 6.3 Constraint Graph......Page 175
  6.3.1 Geometric Elements and Degrees of Freedom......Page 176
  6.3.3 Compound Geometric Elements......Page 177
  6.3.4 Serializable Graphs......Page 178
  6.3.6 Triangle Decomposability......Page 180
  6.3.7 Generic Solvability and the Church-Rosser Property......Page 182
  6.3.8 2D and 3D Graphs......Page 184
 6.4 Solver......Page 185
  6.4.1 2D Triangle-Decomposable Constraint Problems......Page 186
  6.4.2 Root Identification and Order Type......Page 187
  6.4.3 Extended Geometric Vocabulary......Page 193
 6.5 Spatial Geometric Constraints......Page 195
 6.6 Under-Constrained Geometric Constraint Problems......Page 198
  7.1 Introduction......Page 208
  7.1.1 Terminology and Basic Concepts......Page 209
  7.1.2 Triangle-Decomposition......Page 211
  7.1.3 Dulmage-Mendelsohn Decomposition......Page 212
  7.1.4 Assur Decomposition......Page 213
  7.1.5 The Frontier Vertex Algorithm......Page 214
  7.1.6 Canonical Decomposition......Page 215
  7.2.1 Numerical Instability of Rigid Body Incidence and Seam Matroid......Page 218
  7.2.2 Optimal Parameterization in Recombination......Page 219
  7.2.3 Reconciling Conflicting Combinatorial Preprocessors......Page 221
  7.4.1 Root Selection and Navigation......Page 222
  7.4.3 Dynamic Maintenance......Page 223
 7.5 Conclusion......Page 224
PartII Distance Geometry, Real Algebraic Geometry, and Configuration Spaces......Page 226
 8.1 Introduction......Page 228
 8.2 Stress Matrices and Gale Matrices......Page 229
 8.3 Dimensional Rigidity Results......Page 231
  8.4.1 Affine Motions......Page 233
  8.4.2 Universal Rigidity Basic Results......Page 234
  8.4.3 Universal Rigidity for Special Graphs......Page 235
 8.5 Glossary......Page 236
 9.1 Introduction......Page 240
 9.2 Metric and Cut Cones and Polytopes......Page 242
 9.3 Hypermetric Cone and Hypermetric Polytope......Page 243
 9.4 Cut and Metric Polytopes of Graphs......Page 245
 9.5 Quasi-Semimetric Polyhedra......Page 249
 9.6 Partial Metrics......Page 251
 9.7 Supermetric and Hemimetric Cones......Page 252
 9.8 Software Computations......Page 255
 10.1 Introduction......Page 260
  10.1.1 Euclidean Distance Cone......Page 261
 10.3 Related Chapters......Page 262
 10.4 Characterizing 2D Graphs with Convex Cayley Configuration Spaces......Page 263
 10.5 Extension to other Norms, Higher Dimensions, and Flattenability......Page 265
  10.5.2 Some Background on the Distance Cone......Page 267
  10.5.3 Genericity and Independence in the Context of Flattenability......Page 269
 10.6 Efficient Realization through Optimal Cayley Modification......Page 272
 10.7 Cayley Configuration Spaces of 1-Dof Tree-Decomposable Linkages in 2D......Page 273
 10.8 Conclusion......Page 277
 11.1 Introduction......Page 280
  11.1.1 Linkages and Joints......Page 281
 11.2 Mechanisms and Algebraic Varieties......Page 282
  11.2.2 Study Parameters......Page 283
  11.2.3 Dual Quaternions......Page 285
  11.2.4 Analyzing Mechanisms via Algebraic Varieties......Page 287
 11.3 Serial Manipulators......Page 289
  11.3.2 Synthesis of Open and Closed Serial Chains......Page 291
 11.4 Parallel Manipulators......Page 293
  11.4.1 Direct and Inverse Kinematics......Page 294
  11.4.2 Singularities and Self-Motions......Page 295
  11.4.3 Open Problems......Page 296
 12.1 Introduction......Page 300
 12.2 Ideals and Varieties......Page 302
 12.3......Page 303
 12.4 Structure of Algebraic Varieties......Page 304
  12.4.1 Zariski Topology......Page 305
  12.4.3 Maps......Page 306
  12.5.1 Algebraic Relaxation......Page 307
  12.5.2 Semi-Algebraic Sets......Page 308
  12.5.3 Certificates......Page 310
PartIII Geometric Rigidty......Page 314
 13.2 Cauchy’s Theorem......Page 316
 13.3 Co-Dimension 2 Results – Bricard Octahedra......Page 317
 13.4 Polyhedral Surfaces......Page 319
 14.1 Introduction......Page 326
 14.2 Tensegrity Frameworks......Page 327
  14.2.3 Packings......Page 331
 14.3 Types of Rigidity......Page 332
  14.3.2 Universal and Dimensional Rigidity......Page 333
  14.3.3 Operations on Tensegrities......Page 335
 14.4 Examples and Applications......Page 336
  14.4.1 Examples......Page 337
  14.4.2 Applications......Page 338
Chapter15 Geometric Conditions of Rigidity in Nongeneric Settings Oleg Karpenkov......Page 344
 15.1 Introduction......Page 345
 15.2 Configuration Space of Tensegrities and its Stratification......Page 346
  15.2.2 Definition of a Tensegrity......Page 347
  15.2.4 Tensegrities on 4 Points in the Plane......Page 348
  15.3.1 Extended Cayley Algebra......Page 349
  15.3.2 Geometric Relations on Configuration Spaces of Points and Lines......Page 351
  15.4.1 Examples in the Plane......Page 352
  15.4.3 Non-parallelizable Tensegrities......Page 353
  15.4.5 Conjecture on Strong Geometric Conditions for Tensegrities......Page 354
 15.5 Surgeries on Graphs......Page 355
   15.6.1.1 Basic Definitions......Page 357
   15.6.1.2 Geometric Conditions for Framed Cycles......Page 358
   15.6.2.1 Definition of Resolution Schemes......Page 359
   15.6.2.3 HF-Surgeries on Completely Generic Resolution Schemes......Page 360
  15.6.4 Framed Cycles Associated to Generic Resolutions of a Graph......Page 362
  15.6.6 Techniques to Construct Geometric Conditions Defining Tensegrities......Page 363
 16.1 Basic Setup......Page 368
 16.2 Connelly’s Sufficiency Theorem......Page 370
 16.3 Hendrickson’s Necessary Conditions......Page 372
  16.3.1 Nonsufficiency......Page 373
 16.5 Randomized Algorithm for Testing Generic Global Rigidity......Page 374
 16.6 Surgery......Page 375
 16.7 Other Spaces......Page 376
 17.1 Introduction......Page 378
 17.2 Projective Transfer of Infinitesimal Rigidity......Page 379
  17.2.1 Coning and Spherical Frameworks......Page 380
  17.2.2 Rigidity Matrices......Page 382
   17.2.2.1 Spherical to Affine Transfer......Page 384
  17.2.3 Equilibrium Stresses......Page 385
  17.2.4 Point-Hyperplane Frameworks......Page 386
  17.2.5 Tensegrity Frameworks......Page 387
 17.3 Projective Frameworks......Page 388
 17.4 Pseudo-Euclidean Geometries......Page 390
 17.5 Transfer of Symmetric Infinitesimal Rigidity......Page 391
  17.5.1 Symmetric Frameworks......Page 392
 17.6 Global Rigidity......Page 393
  17.6.1 Universal Rigidity......Page 395
  17.6.2 Projective Transformations......Page 396
 17.7 Summary and Related Topics......Page 397
PartIV Combinatorial Rigidity......Page 402
Chapter18 Planar Rigidity Brigitte Servatius and Herman Servatius......Page 404
 18.1 Rigidity of Bar and Joint Frameworks......Page 405
  18.1.1 Rigidity Matrix and Augmented Rigidity Matrices......Page 407
  18.1.2 Rigidity Matrix as a Transformation......Page 409
  18.1.3 The Infinitesimal Rigidity Matroid of a Framework......Page 411
 18.2 Abstract Rigidity Matroids......Page 413
  18.2.1 Characterizations of A2 and (A2)?......Page 414
  18.2.2 The 2-Dimensional Generic Rigidity Matroid......Page 416
  18.2.3 Cycles in G2(n)......Page 417
  18.2.4 Rigid Components of G2(G)......Page 418
  18.2.5 Representability of G2(n)......Page 420
 18.3 Rigidity and Connectivity......Page 422
  18.3.1 Birigidity......Page 423
  18.3.2 Tree Decomposition Theorems......Page 424
   18.3.2.1 Computation of Independence in G2(n)......Page 425
   18.3.3.1 Isostatic Pinned Framework......Page 427
  18.3.4 Body and Pin Structures......Page 433
  18.3.5 Rigidity of Random Graphs......Page 434
 19.1 Introduction......Page 440
 19.2 Rigidity in Rd......Page 441
  19.2.1 Inductive Operations on Frameworks......Page 443
  19.2.2 Recursive Characterizations of Graphs......Page 445
  19.2.3 Combinatorial Characterizations of Rigidity......Page 448
 19.3 Body-Bar, Body-Hinge, Molecular, etc......Page 449
  19.3.1 Geometry and Combinatorics......Page 450
 19.4 Further Rigidity Contexts......Page 451
  19.4.2 Infinite Frameworks......Page 452
  19.4.3 Surfaces......Page 453
  19.4.7 Nearly Generic Frameworks......Page 455
 19.5 Summary Tables......Page 456
Chapter20 Rigidity of Body-Bar-Hinge Frameworks Csaba Kir´aly and Shin-ichi Tanigawa......Page 462
  20.1.1 Body-Bar Frameworks......Page 463
  20.1.2 Body-Hinge Frameworks......Page 467
  20.1.3 Body-Bar-Hinge Frameworks......Page 469
  20.2.2 Body-Hinge Frameworks......Page 470
 20.3 Other Related Models......Page 471
  20.3.2 Identified Body-Hinge Frameworks......Page 472
  20.3.4 Molecular Frameworks......Page 473
  20.3.5 Body-Pin Frameworks......Page 475
  20.3.6 Body-Bar Frameworks with Boundaries......Page 476
  20.4.1 Body-Bar Frameworks......Page 477
  20.4.2 Body-Hinge Frameworks......Page 478
 20.5 Graph Theoretical Aspects......Page 479
  20.5.1 Tree Packing and Connectivity......Page 480
  20.5.4 Algorithms......Page 482
Chapter21 Global Rigidity of Two-Dimensional Frameworks Bill Jackson, Tibor Jord´an, and Shin-Ichi Tanigawa......Page 488
 21.1 Introduction......Page 489
  21.2.1 Stress Matrix Characterization in Rd......Page 490
 21.3 Graph Operations......Page 491
 21.4 Characterization of Global Rigidity in R1 and R2......Page 493
 21.5 The Rigidity Matroid......Page 494
  21.5.3 Rd-Connected Graphs......Page 495
  21.6.1 Highly Connected Graphs......Page 497
  21.6.3 Vertex Transitive Graphs......Page 498
  21.6.5 Random Graphs......Page 499
  21.6.7 Squares of Gaphs, Line Graphs, and Zeolites......Page 500
  21.7.1 Globally Linked Pairs of Vertices......Page 501
  21.7.3 Globally Loose Pairs......Page 503
  21.7.5 The Number of Non-Equivalent Realizations......Page 504
  21.7.6 Stability Lemma and Neighborhood Results......Page 505
 21.8 Direction Constraints......Page 506
  21.8.1 Parallel Drawings......Page 507
  21.8.2 Direction-Length Global Rigidity......Page 508
 21.10Optimization Problems......Page 509
 22.1 Introduction......Page 514
  22.1.3 Constraint Graphs and Frameworks......Page 515
 22.2 Point-Line Graphs and Frameworks......Page 517
  22.2.1 Point-Line Frameworks and the Rigidity Map......Page 518
  22.2.2 The Rigidity Matrix......Page 519
  22.2.4 Affine Properties of the Point-Line Rigidity Matrix......Page 521
  22.2.5 Fixed-Slope Point-Line Frameworks......Page 522
  22.3.1 A Count Matroid for Point-Line Graphs......Page 523
  22.3.2 A Characterization of Independence in MPL(G) when G is Naturally Bi-partite......Page 526
  22.3.4 The Rank Function forPL(G)......Page 528
  22.4.2 Point-Hyperplane Frameworks in Rd......Page 529
 22.5 Direction-Length Frameworks......Page 530
 23.1 Overview......Page 532
  23.2.1 Glossary......Page 533
  23.2.2 Getting to Know Body-and-Cad Frameworks......Page 534
  23.2.3 Formalization of the Algebraic Setting......Page 536
  23.2.4 Building a 3D Body-and-Cad Framework......Page 539
  23.3.1 Glossary......Page 540
   23.3.2.1 Primitive Angular and Blind Constraints......Page 542
  23.4.1 Glossary......Page 544
  23.4.3 Characterizing Generic Body-and-Cad Rigidity......Page 545
  23.4.4 Algorithms......Page 546
 23.5 Open Questions......Page 549
 24.1 Introduction......Page 552
  24.1.1 Glossary......Page 553
  24.2.1 Points of Differentiability......Page 554
  24.2.2 The Rigidity Matrix......Page 555
  24.2.3 Framework Colors......Page 556
  24.2.5 Path Chasing......Page 557
  24.2.6 Symmetry......Page 558
 24.3 Rigidity of Graphs......Page 562
  24.3.2 Regular Points......Page 563
  24.3.3 Symmetric Isostatic Placements......Page 564
  24.3.4 Symmetric Tree Decompositions......Page 566
 25.1 Introduction......Page 570
  25.2.1 Glossary......Page 571
  25.2.2 Symmetry-Adapted Maxwell Counts......Page 572
  25.2.3 Characterizations of Symmetric Isostatic Graphs......Page 575
  25.3.1 Glossary......Page 576
  25.3.2 Symmetric Motions and the Orbit Rigidity Matrix......Page 578
  25.3.3 Characterizations of Forced-Symmetric Rigid Graphs......Page 580
  25.4.1 Glossary......Page 581
  25.4.2 Phase-Symmetric Orbit Rigidity Matrices......Page 583
  25.4.3 Characterizations of Symmetric Infinitesimally Rigid Graphs......Page 584
  25.5.1 Glossary......Page 586
  25.5.2 Maxwell Counts for Periodic Rigidity......Page 587
  25.5.3 Characterizations of Periodic Rigid Graphs......Page 588
Index......Page 594