×

Universal rigidity of bar frameworks via the geometry of spectrahedra. (English) Zbl 1360.90184

Summary: A bar framework \((G,p)\) in dimension \(r\) is a graph \(G\) whose nodes are points \(p^1,\dots,p^n\) in \(\mathbb {R}^r\) and whose edges are line segments between pairs of these points. Two frameworks \((G,p)\) and \((G,q)\) are equivalent if each edge of \((G,p)\) has the same (Euclidean) length as the corresponding edge of \((G,q)\). A pair of non-adjacent vertices \(i\) and \(j\) of \((G,p)\) is universally linked if \(||p^i-p^j|| = ||q^i-q^j||\) in every framework \((G,q)\) that is equivalent to \((G,p)\). Framework \((G,p)\) is universally rigid iff every pair of non-adjacent vertices of \((G,p)\) is universally linked. In this paper, we present a unified treatment of the universal rigidity problem based on the geometry of spectrahedra. A spectrahedron is the intersection of the positive semidefinite cone with an affine space. This treatment makes it possible to tie together some known, yet scattered, results and to derive new ones. Among the new results presented in this paper are: (1) The first sufficient condition for a given pair of non-adjacent vertices of \((G,p)\) to be universally linked. (2) A new, weaker, sufficient condition for a framework \((G,p)\) to be universally rigid thus strengthening the existing known condition. An interpretation of this new condition in terms of the Strong Arnold Property is also presented.

MSC:

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

References:

[1] Alfakih, A.Y.: Graph rigidity via Euclidean distance matrices. Linear Algebra Appl. 310, 149-165 (2000) · Zbl 0965.05069 · doi:10.1016/S0024-3795(00)00066-5
[2] Alfakih, A.Y.: On dimensional rigidity of bar-and-joint frameworks. Discrete Appl. Math. 155, 1244-1253 (2007) · Zbl 1116.52007 · doi:10.1016/j.dam.2006.11.011
[3] Alfakih, A.Y.: On the universal rigidity of generic bar frameworks. Contrib. Disc. Math. 5, 7-17 (2010) · Zbl 1189.52020
[4] Alfakih, A.Y.: On bar frameworks, stress matrices and semidefinite programming. Math. Program. Ser. B 129, 113-128 (2011) · Zbl 1225.90095 · doi:10.1007/s10107-010-0389-z
[5] Alfakih, A.Y., Khandani, A., Wolkowicz, H.: Solving Euclidean distance matrix completion problems via semidefinite programming. Comput. Optim. Appl. 12, 13-30 (1999) · Zbl 1040.90537 · doi:10.1023/A:1008655427845
[6] Alfakih, A.Y., Nyugen, V.-H.: On affine motions and universal rigidity of tensegrity frameworks. Linear Algebra Appl. 439, 3134-3147 (2013) · Zbl 1285.52010 · doi:10.1016/j.laa.2013.08.016
[7] Alfakih, A.Y., Taheri, N., Ye, Y.: On stress matrices of \[(d+1\] d+1)-lateration frameworks in general position. Math. Program. 137, 1-17 (2013) · Zbl 1263.90049 · doi:10.1007/s10107-011-0480-0
[8] Alfakih, A.Y., Ye, Y.: On affine motions and bar frameworks in general positions. Linear Algebra Appl. 438, 31-36 (2013) · Zbl 1262.52020 · doi:10.1016/j.laa.2012.08.031
[9] Alizadeh, F., Haeberly, J.A., Overton, M.L.: Complementarity and nondegeneracy in semidefinite programming. Math. Program. Ser. B 77, 111-128 (1997) · Zbl 0890.90141
[10] Barker, G.P., Carlson, D.: Cones of diagonally dominant matrices. Pac. J. Math. 57, 15-31 (1975) · Zbl 0283.52005 · doi:10.2140/pjm.1975.57.15
[11] Connelly, R.: Rigidity and energy. Invent. Math. 66, 11-33 (1982) · Zbl 0485.52001 · doi:10.1007/BF01404753
[12] Connelly, R.: Generic global rigidity. Discrete Comput. Geom. 33, 549-563 (2005) · Zbl 1072.52016 · doi:10.1007/s00454-004-1124-4
[13] Connelly, R., Gortler, S.J.: Iterative universal rigidity. Discrete Comput. Geom. 53, 847-877 (2015) · Zbl 1314.05137 · doi:10.1007/s00454-015-9670-5
[14] Critchley, F.: On certain linear mappings between inner-product and squared distance matrices. Linear Algebra Appl. 105, 91-107 (1988) · Zbl 0644.15003 · doi:10.1016/0024-3795(88)90006-7
[15] Gale, D.: Neighboring vertices on a convex polyhedron. In Linear inequalities and related system, pp 255-263. Princeton University Press, Princeton(1956) · Zbl 0072.37805
[16] Gortler, S.J., Thurston, D.P.: Characterizing the universal rigidity of generic frameworks. Discrete Comput. Geom. 51, 1017-1036 (2014) · Zbl 1298.05303 · doi:10.1007/s00454-014-9590-9
[17] Gower, J.C.: Properties of Euclidean and non-Euclidean distance matrices. Linear Algebra Appl. 67, 81-97 (1985) · Zbl 0569.15016 · doi:10.1016/0024-3795(85)90187-9
[18] Grünbaum, B.: Convex polytopes. Wiley, New York (1967) · Zbl 0163.16603
[19] Jordán, T., Nguyen, V.-H.: On universally rigid frameworks on the line. Technical report, Egerváry Research Group (2012) · Zbl 1344.52013
[20] Laurent, M., Varvitsiotis, A.: Positive semidefinite matrix completion, universal rigidity and the strong Arnold property. Linear Algebra Appl. 452, 292-317 (2014) · Zbl 1291.90165 · doi:10.1016/j.laa.2014.03.015
[21] Pataki, G.: The geometry of semidefinite programing. In: Wolkowicz, H., Saigal, R., Vandenberghe, L., (eds.) Handbook of Semidefinite Programming: Theory, Algorithms and Applications, pp. 29-65. Kluwer Academic publishers (2000) · Zbl 0957.90531
[22] Ramana, M., Goldman, A.J.: Some geometric results in semi-definite programming. J. Glob. Optim. 7, 33-50 (1995) · Zbl 0839.90093 · doi:10.1007/BF01100204
[23] Rockafellar, R.T.: Convex Analysis. Princeton University Press, Princeton (1970) · Zbl 0193.18401 · doi:10.1515/9781400873173
[24] Schoenberg, I.J.: Remarks to Maurice Fréchet’s article: Sur la définition axiomatique d’une classe d’espaces vectoriels distanciés applicables vectoriellement sur l’espace de Hilbert. Ann. Math. 36, 724-732 (1935) · Zbl 0012.30703 · doi:10.2307/1968654
[25] Young, G., Householder, A.S.: Discussion of a set of points in terms of their mutual distances. Psychometrika 3, 19-22 (1938) · JFM 64.1302.04 · doi:10.1007/BF02287916
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.