Abstract
In 2005, Bob Connelly showed that a generic framework in \({\mathbb {R}}^d\) is globally rigid if it has a stress matrix of maximum possible rank, and that this sufficient condition for generic global rigidity is preserved by the 1-extension operation. His results gave a key step in the characterisation of generic global rigidity in the plane. We extend these results to frameworks on surfaces in \({\mathbb {R}}^3\). For a framework on a family of concentric cylinders, cones or ellipsoids, we show that there is a natural surface stress matrix arising from assigning edge and vertex weights to the framework, in equilibrium at each vertex. In the case of cylinders and ellipsoids, we show that having a maximum-rank stress matrix is sufficient to guarantee generic global rigidity on the surface. We then show that this sufficient condition for generic global rigidity is preserved under 1-extension and use this to make progress on the problem of characterising generic global rigidity on the cylinder.
Similar content being viewed by others
Notes
We can consider \(\det M\) as a polynomial in the coordinates of \((p(v_1),p(v_2),p(v_3))\). If \(\det M=0\), then genericness would imply that this polynomial evaluates to 0 at all points in \(S(r_1)\times S(r_2)\times S(r_3)\). It is straightforward to show that this is not the case by finding points \((p_1,p_2,p_3)\in S(r_1)\times S(r_2)\times S(r_3)\) at which the polynomial is non-zero. When \({S}={\mathcal {Y}}(r)\), we can take \(p_1=(\sqrt{r_1},0,0)\), \(p_2=(0,\sqrt{r_2},0)\) and \(p_3=(\sqrt{r_3},0,1)\); when \({S}={\mathcal {C}}(r)\), we can take \(p_1=(\sqrt{r_1},0,1)\), \(p_2=(\sqrt{r_2},0,-1)\) and \(p_3=(0,\sqrt{r_3},1)\); and when \({S}={\mathcal {E}}(r)\), we can take \(p_1=(\sqrt{r_1},0,0)\), \(p_2=(0,\frac{\sqrt{r_2}}{\sqrt{\alpha }},0)\) and \(p_3=(0,0,\frac{\sqrt{r_3}}{\sqrt{\beta }})\).
References
Abbott, T.: Generalizations of Kempeβs universality theorem, Masterβs Thesis, Massachusetts Institute of Technology. http://web.mit.edu/tabbott/www/papers/mthesis.pdf (2008)
Basu, S., Pollack, R., Roy, M.-F.: Algorithms in Real Algebraic Geometry. Springer, Berlin (2004)
Bochnak, J., Coste, M., Roy, M.-F.: Real Algebraic Geometry. Springer, Berlin (1998)
Connelly, R.: Rigidity and energy. Invent. Math. 66, 11β33 (1982)
Connelly, R.: On generic global rigidity. In: Applied Geometry and Discrete Mathematics. DIMACS Series Discrete Mathematics and Theoretical Computer Science, vol. 4, pp. 147β155 (1991)
Connelly, R.: Generic global rigidity. Discrete Comput. Geom. 33, 549β563 (2005)
Connelly, R., Whiteley, W.: Global rigidity: the effect of coning. Discrete Comput. Geom. 43(4), 717β735 (2010)
Gortler, S., Healy, A., Thurston, D.: Characterizing generic global rigidity. Am. J. Math. 132(4), 897β939 (2010)
Hendrickson, B.: Conditions for unique graph realisations. SIAM J. Comput. 21(1), 65β84 (1992)
Laman, G.: On graphs and the rigidity of plane skeletal structures. J. Eng. Math. 4, 331β340 (1970)
Jackson, B., JordΓ‘n, T.: Connected rigidity matroids and unique realisations of graphs. J. Comb. Theory B 94, 1β29 (2005)
Jackson, B., Keevash, P.: Necessary conditions for global rigidity of direction-length frameworks. Discrete Comput. Geom. 46, 72β85 (2011)
Jackson, B., McCourt, T., Nixon, A.: Necessary conditions for the generic global rigidity of frameworks on surfaces. Discrete Comput. Geom. 52(2), 344β360 (2014)
Nixon, A.: A constructive characterisation of circuits in the simple (2,2)-sparsity matroid. Eur. J. Comb. 42, 92β106 (2014)
Nixon, A., Owen, J., Power, S.: Rigidity of frameworks supported on surfaces. SIAM J. Discrete Math. 26, 1733β1757 (2012)
Nixon, A., Owen, J., Power, S.: A characterization of generically rigid frameworks on surfaces of revolution. SIAM J. Discrete Math. 28(4), 2008β2028 (2014)
Saxe, J.: Embeddability of weighted graphs in k-space is strongly NP-hard. In: Proceedings of the Seventeenth Annual Allerton Conference on Communication, Control, and Computing, Monticello, IL, 10β12 Oct 1979
Spivak, M.: A Comprehensive Introduction to Differential Geometry, vol. 1. Publish or Perish, Wilmington (1999)
Whiteley, W.: Some matroids from discrete applied geometry, In: Matroid Theory (Seattle, WA, 1995). Contemporary Mathematics, vol. 197. American Mathematical Society, Providence, RI (1996)
Acknowledgments
We would like to thank the School of Mathematics, University of Bristol, for providing partial financial support for this research. We would also like to thank Lee Butler for helpful discussions concerning semi-algebraic sets and Bob Connelly for many helpful discussions.
Author information
Authors and Affiliations
Corresponding author
Additional information
Editor in Charge: JΓ‘nos Pach
Rights and permissions
About this article
Cite this article
Jackson, B., Nixon, A. Stress Matrices and Global Rigidity of Frameworks on Surfaces. Discrete Comput Geom 54, 586β609 (2015). https://doi.org/10.1007/s00454-015-9724-8
Received:
Revised:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00454-015-9724-8