Universal rigidity of bar frameworks via the geometry of spectrahedra

A. Y. Alfakih ()
Additional contact information
A. Y. Alfakih: University of Windsor

Journal of Global Optimization, 2017, vol. 67, issue 4, No 10, 909-924

Abstract: Abstract A bar framework (G, p) in dimension r is a graph G whose nodes are points $$p^1,\ldots ,p^n$$ p 1 , … , p n in $$\mathbb {R}^r$$ 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||$$ | | p i - p j | | = $$||q^i-q^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.

Keywords: Semidefinite programming; Universal rigidity; Bar frameworks; Spectrahedra; Stress matrices; Gale transform; Cayley configuration space; Distance geometry; Strong Arnold Property; 90C22; 52C25; 05C62 (search for similar items in EconPapers)
Date: 2017
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10898-016-0448-y Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jglopt:v:67:y:2017:i:4:d:10.1007_s10898-016-0448-y

Ordering information: This journal article can be ordered from
http://www.springer. ... search/journal/10898

DOI: 10.1007/s10898-016-0448-y

Access Statistics for this article

Journal of Global Optimization is currently edited by Sergiy Butenko

More articles in Journal of Global Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().