Universal rigidity of bar frameworks via the geometry of spectrahedra

DOI10.1007/S10898-016-0448-YzbMATH Open1360.90184arXiv1504.00578OpenAlexW2460667336MaRDI QIDQ522288FDOQ522288

Abdo Y. Alfakih

Publication date: 28 April 2017

Published in: Journal of Global Optimization (Search for Journal in Brave)

Abstract: A bar framework (G,p) in dimension r is a graph G whose vertices are points p^1,...,p^n in 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: (i) A sufficient condition for a given pair of non-adjacent vertices of (G,p) to be universally linked. (ii) 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 and transversal intersection is also presented.

Full work available at URL: https://arxiv.org/abs/1504.00578

Recommendations

• Characterizing the universal rigidity of generic frameworks
• On bar frameworks, stress matrices and semidefinite programming
• Iterative universal rigidity
• On the universal rigidity of generic bar frameworks
• On affine motions and bar frameworks in general position

zbMATH Keywords

semidefinite programmingstrong Arnold propertydistance geometryspectrahedrauniversal rigiditybar frameworksstress matricesCayley configuration spacegale transform

Mathematics Subject Classification ID

Semidefinite programming (90C22) Graph representations (geometric and intersection representations, etc.) (05C62) Rigidity and flexibility of structures (aspects of discrete geometry) (52C25)

Cites Work

• Convex Analysis
• Remarks to Maurice Frechet's article ``Sur la definition axiomatique d'une classe d'espaces vectoriels distancies applicables vectoriellement sur l'espace de Hilbert
• Generic global rigidity
• Title not available (Why is that?)
• Properties of Euclidean and non-Euclidean distance matrices
• On certain linear mappings between inner-product and squared-distance matrices
• Title not available (Why is that?)
• Complementarity and nondegeneracy in semidefinite programming
• Some geometric results in semidefinite programming
• Title not available (Why is that?)
• Positive semidefinite matrix completion, universal rigidity and the strong Arnold property
• Title not available (Why is that?)
• Solving Euclidean distance matrix completion problems via semidefinite progrmming
• Rigidity and energy
• Characterizing the universal rigidity of generic frameworks
• Cones of diagonally dominant matrices
• On dimensional rigidity of bar-and-joint frameworks
• On affine motions and bar frameworks in general position
• Iterative universal rigidity
• On affine motions and universal rigidity of tensegrity frameworks
• Title not available (Why is that?)
• On bar frameworks, stress matrices and semidefinite programming
• On stress matrices of \((d + 1)\)-lateration frameworks in general position
• Graph rigidity via Euclidean distance matrices

Cited In (2)

• On rigidity of unit-bar frameworks
• On yielding and jointly yielding entries of Euclidean distance matrices

This page was built for publication: Universal rigidity of bar frameworks via the geometry of spectrahedra

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q522288)