×

Iterative universal rigidity. (English) Zbl 1314.05137

Summary: A bar framework determined by a finite graph \(G\) and a configuration \(p =(p_1,\dots , p_n) \) in \(\mathbb {R}^d\) is universally rigid if it is rigid in any \(\mathbb {R}^D \supset \mathbb {R}^d\). We provide a characterization of universal rigidity for any graph \(G\) and any configuration \(p\) in terms of a sequence of affine subsets of the space of configurations. This corresponds to a facial reduction process for closed finite-dimensional convex cones.

MSC:

05C62 Graph representations (geometric and intersection representations, etc.)
52C25 Rigidity and flexibility of structures (aspects of discrete geometry)
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Abbott, T.G.: Generalizations of Kempe’s universality theorem. Masters thesis, Massachusetts Institute of Technology (2008). http://dspace.mit.edu/handle/1721.1/44375 · Zbl 1211.90166
[2] Alfakih, A.Y.: On dimensional rigidity of bar-and-joint frameworks. Discrete Appl. Math. 155(10), 1244-1253 (2007) · Zbl 1116.52007 · doi:10.1016/j.dam.2006.11.011
[3] Alfakih, A.Y.: On bar frameworks, stress matrices and semidefinite programming. Math. Program. 129(1, Ser. B), 113-128 (2011) · Zbl 1225.90095
[4] Alfakih, A.Y., Ye, Y.: On affine motions and bar frameworks in general position. Linear Algebra Appl. 438(1), 31-36 (2013) · Zbl 1262.52020 · doi:10.1016/j.laa.2012.08.031
[5] Alfakih, A.Y., Anjos, M.F., Piccialli, V., Wolkowicz, H.: Euclidean distance matrices, semidefinite programming and sensor network localization. Port. Math. 68(1), 53-102 (2011) · Zbl 1223.51017 · doi:10.4171/PM/1881
[6] Belk, M., Connelly, R.: Realizability of graphs. Discrete Comput. Geom. 37(2), 125-137 (2007) · Zbl 1114.05067 · doi:10.1007/s00454-006-1284-5
[7] Bezdek, K., Connelly, R.: Two-distance preserving functions from Euclidean space. In: Proc. Distance Geometry and Rigidity, Budapest, 1999. Period. Math. Hung. 39(1-3), 185-200 (1999) · Zbl 0968.51009
[8] Blum, L., Shub, M., Smale, S.: On a theory of computation over the real numbers: NP completeness, recursive functions and universal machines. Bull. Amer. Math. Soc. 21(1), 1-46 (1989) · Zbl 0681.03020
[9] Borwein, J. M., Wolkowicz, H.: Facial reduction for a cone-convex programming problem. J. Aust. Math. Soc. Ser. A 30(3), 369-380 (1980/81) · Zbl 0464.90086
[10] Connelly, R.: Rigidity and energy. Invent. Math. 66(1), 11-33 (1982) · Zbl 0485.52001 · doi:10.1007/BF01404753
[11] Connelly, R.: Rigidity. Handbook of Convex Geometry, Vol. A, B, pp. 223-271. North-Holland, Amsterdam (1993) · Zbl 0788.52001
[12] Connelly, R.: Generic global rigidity. Discrete Comput. Geom. 33(4), 549-563 (2005) · Zbl 1072.52016 · doi:10.1007/s00454-004-1124-4
[13] Connelly, R.: What is \[\ldots \]… a tensegrity? Notices Am. Math. Soc. 60(1), 78-80 (2013) · Zbl 1284.05001 · doi:10.1090/noti933
[14] Connelly, R.; Senechal, M. (ed.), Tensegrities and global rigidity, 267-278 (2013), New York · doi:10.1007/978-0-387-92714-5_21
[15] Connelly, R., Back, A.: Mathematics and tensegrity. Am. Sci. 86(2), 142-151 (1998) · doi:10.1511/1998.2.142
[16] Connelly, R., Whiteley, W.: Second-order rigidity and prestress stability for tensegrity frameworks. SIAM J. Discrete Math. 9(3), 453-491 (1996) · Zbl 0855.52006 · doi:10.1137/S0895480192229236
[17] Connelly, R., Whiteley, W.: Global rigidity: the effect of coning. Discrete Comput. Geom. 43, 717-735 (2010) · Zbl 1190.52018 · doi:10.1007/s00454-009-9220-0
[18] Connelly, R., Terrell, M.: Tenségrités symétriques globalement rigides. Struct. Topol. 21, 59-78 (1995). Dual French-English text · Zbl 0841.52013
[19] Connelly, R., Jordán, T., Whiteley, W.: Generic global rigidity of body-bar frameworks. J. Comb. Theory Ser. B 103(6), 689-705 (2013) · Zbl 1280.05092
[20] Gortler, S.J., Thurston, D.P.: Characterizing the universal rigidity of generic frameworks. Discrete Comput. Geom. 51(4), 1017-1036 (2014) · Zbl 1298.05303 · doi:10.1007/s00454-014-9590-9
[21] Gortler, S.J., Healy, A.D., Thurston, D.P.: Characterizing generic global rigidity. Am. J. Math. 132(132), 897-939 (2010) · Zbl 1202.52020 · doi:10.1353/ajm.0.0132
[22] Gortler, S.J., Gotsman, C., Ligang, L., Thurston, D.P.: On affine rigidity, pp. 1-20. arXiv:1011.5553v3 (2013) · Zbl 1404.05136
[23] Grünbaum, B.: Convex Polytopes. Graduate Texts in Mathematics, 2nd ed., vol. 221. Springer, New York (2003) · Zbl 0479.51015
[24] Jackson, B., Jordán, T.: Connected rigidity matroids and unique realizations of graphs. J. Comb. Theory, Ser. B 94(1), 1-29 (2005) · Zbl 1076.05021
[25] Jackson, B., Jordán, T., Szabadka, Z.: Globally linked pairs of vertices in equivalent realizations of graphs. Discrete Comput. Geom. 35(3), 493-512 (2006) · Zbl 1088.05056 · doi:10.1007/s00454-005-1225-8
[26] Javanmard, A., Montanari, A.: Localization from incomplete noisy distance measurements. Found. Comput. Math. 13(3), 297-345 (2013) · Zbl 1269.05098 · doi:10.1007/s10208-012-9129-5
[27] Jordán, T., Nguyen, V.-H.: On universally rigid frameworks on the line. Technical Report TR-2012-10, Egerváry Research Group on Combinatorial Optimization, Budapest, Hungary, July 14, pp. 1-13 (2012) · Zbl 1298.05303
[28] Krislock, N., Wolkowicz, H.: Explicit sensor network localization using semidefinite representations and facial reductions. SIAM J. Optim. 20(5), 2679-2708 (2010) · Zbl 1229.90250 · doi:10.1137/090759392
[29] Laurent, M., Varvitsiotis, A.: The Gram dimension of a graph. In: Combinatorial Optimization. Lecture Notes in Computer Science, vol. 7422, pp. 356-367 (2012) · Zbl 1370.05196
[30] Man-Cho So, A., Ye, Y.: A semidefinite programming approach to tensegrity theory and realizability of graphs. In: Proceedings of the Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 766-775. ACM, New York (2006) · Zbl 1192.90137
[31] Masic, M., Skelton, R.E., Gill, P.E.: Algebraic tensegrity form-finding. Int. J. Solids Struct. 42(16-17), 4833-4858 (2005) · Zbl 1119.74464 · doi:10.1016/j.ijsolstr.2005.01.014
[32] Pach, J., Pollack, R., Welzl, E.: Weaving patterns of lines and line segments in space. Algorithms (Tokyo, 1990). Lecture Notes in Computer Science, vol. 450. Springer, Berlin (1990) · Zbl 0788.68146
[33] Pach, J., Pollack, R., Welzl, E.: Weaving patterns of lines and line segments in space. Algorithmica 9(6), 561-571 (1993). Selections from SIGAL International Symposium on Algorithms (Tokyo, 1990) · Zbl 0788.68146
[34] Pak, I., Vilenchik, D.: Constructing uniquely realizable graphs. Discrete Comput. Geom. 50(4), 1051-1071 (2013) · Zbl 1280.05092 · doi:10.1007/s00454-013-9545-6
[35] Pataki, G.: Strong duality in conic linear programming: facial reduction and extended duals. arXiv:1301.7717v3 (2009) · Zbl 1282.90231
[36] Ramana, M.V.: An exact duality theory for semidefinite programming and its complexity implications. Math. Program. 77(2, Ser. B), 129-162 (1997). Semidefinite programming · Zbl 0890.90144
[37] Recski, A.: Combinatorial conditions for the rigidity of tensegrity frameworks. Horizons of Combinatorics. Bolyai Society Mathematical Studies, vol. 17, pp. 163-177. Springer, Berlin (2008) · Zbl 1152.52010
[38] Roth, B., Whiteley, W.: Tensegrity frameworks. Trans. Am. Math. Soc. 265(2), 419-446 (1981) · Zbl 0479.51015 · doi:10.1090/S0002-9947-1981-0610958-6
[39] Saxe, J.B.: Embeddability of weighted graphs in k-space is strongly np-hard. In: Proceedings of 17th Allerton Conference in Communications, Control and Computing, pp. 480-489 (1979) · Zbl 1116.52007
[40] Schek, H.-J.: The force density method for form finding and computation of general networks. Comput. Methods Appl. Mech. Eng. 3(1), 115-134 (1974) · doi:10.1016/0045-7825(74)90045-0
[41] Skelton, R.E., de Oliveira, M.C.: Optimal tensegrity structures in bending: the discrete Michell truss. J. Franklin Inst. 347(1), 257-283 (2010) · Zbl 1298.49062 · doi:10.1016/j.jfranklin.2009.10.009
[42] Tay, T.-S.: Rigidity of multigraphs. I. Linking rigid bodies in \[n\] n-space. J. Comb. Theory, Ser. B 36(1), 95-112 (1984) · Zbl 0522.05066
[43] Tay, T.-S., Whiteley, W.: Recent advances in the generic rigidity of structures. Struct. Topol. 9, 31-38 (1984). Dual French-English text · Zbl 0541.51021
[44] Whiteley, W.: Rigidity and polarity. I. Statics of sheet structures. Geom. Dedicata 22(3), 329-362 (1987) · Zbl 0618.51006 · doi:10.1007/BF00147940
[45] Whiteley, W.: Rigidity and polarity. II. Weaving lines and tensegrity frameworks. Geom. Dedicata 30(3), 255-279 (1989) · Zbl 0675.51008 · doi:10.1007/BF00181341
[46] Whiteley, W.: Rigidity and scene analysis. Handbook of Discrete and Computational Geometry. CRC Press Series on Discrete Mathematics and its Applications, pp. 893-916. CRC Press, Boca Raton (1997) · Zbl 0902.52008
[47] Ye, Y.: Semidefinite programming and universal rigidity. Fields Institute Lecture, pp. 1-92 (2011)
[48] Zhang, L.-Y., Li, Y., Cao, Y.-P., Feng, X.-Q., Gao, H.: Self-equilibrium and super-stability of truncated regular polyhedral tensegrity structures: a unified analytical solution. Proc. R. Soc. Lond., Ser. A 468(2147), 3323-3347 (2012) · Zbl 1371.34082
[49] Zhu, Z., Man-Cho So, A., Ye, Y.: Universal rigidity and edge sparsification for sensor network localization. SIAM J. Optim. 20(6), 3059-3081 (2010) · Zbl 1211.90166 · doi:10.1137/090772009
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.