Universal Rigidity of Bar Frameworks via the Geometry of Spectrahedra

preprint2015arXivOpen access

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.

Explore this paper’s authors, topics and related work.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Reviews 0

Write a reviewWrite

No reviews yet.

Discussion 0

Add a commentWrite

No comments yet.