More Web Proxy on the site http://driver.im/

article

Generic Global Rigidity

Author:

Robert ConnellyAuthors Info & Claims

Discrete & Computational Geometry, Volume 33, Issue 4

Pages 549 - 563

https://doi.org/10.1007/s00454-004-1124-4

Published: 01 April 2005 Publication History

Abstract

Suppose a finite configuration of labeled points p = (p1,. . .,pn) in Ed is given along with certain pairs of those points determined by a graph G such that the coordinates of the points of p are generic, i.e., algebraically independent over the integers. If another corresponding configuration q = (q1,. . .,qn) in Ed is given such that the corresponding edges of G for p and q have the same length, we provide a sufficient condition to ensure that p and q are congruent in Ed. This condition, together with recent results of Jackson and Jordán, give necessary and sufficient conditions for a graph being generically globally rigid in the plane.

References

[1]

Asimow, Len; Roth, Ben. The rigidity of graphs. Trans. Amer. Math. Soc. 245 (1978), 279-289. MR 80i:57004a.

[2]

Asimow, Len; Roth, Ben. The rigidity of graphs, II. J. Math. Anal. Appl. 68(1) (1979), 171-190. MR 80i:57004b.

[3]

Berg, Alex R.; Jordán, Tibor. A proof of Connelly's conjecture on 3-connected circuits of the rigidity matroid. J. Combin. Theory Ser. B, 88 (2003) 77-97.

Digital Library

[4]

Benedetti, Riccardo; Risler, Jean-Jacques. Real algebraic and semi-algebraic sets. Actualités Mathématiques. [Current Mathematical Topics] Hermann, Paris, 1990, 340 pp. ISBN: 2-7056-6144-1. MR 99a:57012.

[5]

Connelly, Robert. Rigidity and energy. Invent. Math. 66(1) (1982), 11-33. MR 83m:52012.

[6]

Connelly, Robert. Generic global rigidity. Applied Geometry and Discrete Mathematics, pp. 147-155; DIMACS Series in Discrete Mathematics and Theoretical Computer Science, 4. American Mathematical Society, Providence, RI, 1991. MR 83m:52012.

[7]

Connelly, Robert. Rigidity. Handbook of Convex Geometry, Vols. A, B, pp. 223-271. North-Holland, Amsterdam, 1993. MR 94j:52041.

[8]

Connelly, Robert; Whiteley, Walter. Second-order rigidity and prestress stability for tensegrity frameworks. SIAM J. Discrete Math. 9(3) (1996), 453-491. MR 97e:52037.

Digital Library

[9]

Gluck, Herman. Almost all simply connected closed surfaces are rigid. Geometric Topology (Proc. Conf., Park City, Utah, 1974), pp. 225-239. Lecture Notes in Mathematics, Vol. 438, Springer-Verlag, Berlin, 1975. MR 53 #4074.

[10]

Guillemin, Victor; Pollack, Alan. Differential Topology. Prentice-Hall, Inc., Englewood Cliffs, NJ, 1974. MR 50 #1276.

[11]

Graver, Jack; Servatius, Brigitte; Servatius, Herman. Combinatorial Rigidity. Graduate Studies in Mathematics, 2. American Mathematical Society, Providence, RI, 1993. MR 95b:52034.

[12]

Hendrickson, Bruce. The Molecule Problem: Determining Conformation from Pairwise Distances. Ph.D dissertation, Cornell University, 1991.

[13]

Hendrickson, Bruce. Conditions for unique graph realizations. SIAM J. Comput. 21(1) (1992), 65-84. MR 92m:05182.

Digital Library

[14]

Hendrickson, Bruce. The molecule problem: exploiting structure in global optimization. SIAM J. Optim. 5(4) (1995), 835-857. MR 96g:90093.

Digital Library

[15]

Jackson, Bill; Jordán, Tibor. Connected rigidity matroids and unique realizations of graphs (preprint) (2003).

[16]

Marker, David. Model Theory. An Introduction. Graduate Texts in Mathematics, 217. Springer-Verlag, New York, 2002.

[17]

Milnor, John W. Topology from the Differentiable Viewpoint. Based on Notes by David W. Weaver. Revised reprint of the 1965 original. Princeton Landmarks in Mathematics. Princeton University Press, Princeton, NJ, 1997. MR 98h:57051.

[18]

Saxe, James B. Embeddability of weighted graphs in k-space is strongly NP-hard. Technical report, Computer Science Department, Carnegie Mellon University, 1979.

[19]

Seidenberg, A. A new decision method for elementary algebra. Ann. of Math. (2) 60, (1954), 365-374. MR 16,209a.

[20]

Tay, Tiong-Seng (SGP-Sing); Whiteley, Walter. Generating isostatic frameworks. (Dual French-English text.) Structural Topology 11 (1985), 21-69. MR 87e:05139.

Cited By

Erskine JBriot SFantoni IChriette A(2024)Singularity Analysis of Rigid Directed Bearing Graphs for Quadrotor FormationsIEEE Transactions on Robotics10.1109/TRO.2023.332419840(139-157)Online publication date: 1-Jan-2024
https://dl.acm.org/doi/10.1109/TRO.2023.3324198
Jordán TVillányi S(2024)Globally Linked Pairs of Vertices in Generic FrameworksCombinatorica10.1007/s00493-024-00094-344:4(817-838)Online publication date: 1-Aug-2024
https://dl.acm.org/doi/10.1007/s00493-024-00094-3
Manam LGovindu VOh ANaumann TGloberson ASaenko KHardt MLevine S(2023)Sensitivity in translation averagingProceedings of the 37th International Conference on Neural Information Processing Systems10.5555/3666122.3668863(62740-62763)Online publication date: 10-Dec-2023
https://dl.acm.org/doi/10.5555/3666122.3668863
Show More Cited By

Generic Global Rigidity
1. Theory of computation
  1. Randomness, geometry and discrete structures

Recommendations

Generic global rigidity of body-bar frameworks

A basic geometric question is to determine when a given framework G(p) is globally rigid in Euclidean space R^d, where G is a finite graph and p is a configuration of points corresponding to the vertices of G. G(p) is globally rigid inR^d if for any ...
Generic global rigidity of body-hinge frameworks

A d-dimensional body-hinge framework is a structure consisting of rigid bodies in d-space in which some pairs of bodies are connected by a hinge, restricting the relative position of the corresponding bodies. The framework is said to be globally rigid ...
Necessary Conditions for the Generic Global Rigidity of Frameworks on Surfaces

A result due in its various parts to Hendrickson, Connelly, and Jackson and Jordán, provides a purely combinatorial characterisation of global rigidity for generic bar-joint frameworks in $${{\mathbb {R}}}^2$$ R 2 . The analogous conditions are known to be insufficient to ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Discrete & Computational Geometry

Discrete & Computational Geometry Volume 33, Issue 4

April 2005

177 pages

ISSN:0179-5376

Issue’s Table of Contents

Copyright © Copyright © 2005 Springer.

Publisher

Springer-Verlag

Berlin, Heidelberg

Publication History

Published: 01 April 2005

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

68
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 14 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Erskine JBriot SFantoni IChriette A(2024)Singularity Analysis of Rigid Directed Bearing Graphs for Quadrotor FormationsIEEE Transactions on Robotics10.1109/TRO.2023.332419840(139-157)Online publication date: 1-Jan-2024
https://dl.acm.org/doi/10.1109/TRO.2023.3324198
Jordán TVillányi S(2024)Globally Linked Pairs of Vertices in Generic FrameworksCombinatorica10.1007/s00493-024-00094-344:4(817-838)Online publication date: 1-Aug-2024
https://dl.acm.org/doi/10.1007/s00493-024-00094-3
Manam LGovindu VOh ANaumann TGloberson ASaenko KHardt MLevine S(2023)Sensitivity in translation averagingProceedings of the 37th International Conference on Neural Information Processing Systems10.5555/3666122.3668863(62740-62763)Online publication date: 10-Dec-2023
https://dl.acm.org/doi/10.5555/3666122.3668863
Bai XWang YPing HXu XLi DWang S(2023)InferLoc: Hypothesis-Based Joint Edge Inference and Localization in Sparse Sensor NetworksACM Transactions on Sensor Networks10.1145/360847720:1(1-28)Online publication date: 12-Jul-2023
https://dl.acm.org/doi/10.1145/3608477
Cruickshank JJackson BTanigawa S(2022)Vertex Splitting, Coincident Realisations, and Global Rigidity of Braced TriangulationsDiscrete & Computational Geometry10.1007/s00454-022-00459-969:1(192-208)Online publication date: 19-Nov-2022
https://dl.acm.org/doi/10.1007/s00454-022-00459-9
Song YBajaj IRabiee RTay W(2021)Anchor-Free Multi-Level Self-Localization in Ad-hoc Networks2021 IEEE Wireless Communications and Networking Conference (WCNC)10.1109/WCNC49053.2021.9417602(1-6)Online publication date: 29-Mar-2021
https://dl.acm.org/doi/10.1109/WCNC49053.2021.9417602
Oba RTanigawa S(2021)Characterizing the universal rigidity of generic tensegritiesMathematical Programming: Series A and B10.1007/s10107-021-01730-2197:1(109-145)Online publication date: 29-Nov-2021
https://dl.acm.org/doi/10.1007/s10107-021-01730-2
Garamvölgyi DJordán T(2021)Graph Reconstruction from Unlabeled Edge LengthsDiscrete & Computational Geometry10.1007/s00454-021-00275-766:1(344-385)Online publication date: 1-Jul-2021
https://dl.acm.org/doi/10.1007/s00454-021-00275-7
Kwon SSun ZAnderson BAhn H(2020)Hybrid rigidity theory with signed constraints and its application to formation shape control in 2-D space2020 59th IEEE Conference on Decision and Control (CDC)10.1109/CDC42340.2020.9303970(518-523)Online publication date: 14-Dec-2020
https://dl.acm.org/doi/10.1109/CDC42340.2020.9303970
Hamaoui M(2019)Non-Iterative MDS Method for Collaborative Network Localization With Sparse Range and Pointing MeasurementsIEEE Transactions on Signal Processing10.1109/TSP.2018.287962367:3(568-578)Online publication date: 1-Feb-2019
https://dl.acm.org/doi/10.1109/TSP.2018.2879623
Show More Cited By

View Options

View options

Media

Figures

Other

Tables

View Issue’s Table of Contents