On affine rigidity

Abstract

We study the properties of affine rigidity of a hypergraph and prove a variety of fundamental results. First, we show that affine rigidity is a generic property (i.e., depends only on the hypergraph, not the particular embedding). Then we prove that a graph is generically neighborhood affinely rigid in d-dimensional space if it is (d+1)-vertex-connected. We also show neighborhood affine rigidity of a graph implies universal rigidity of its squared graph. Our results, and affine rigidity more generally, have natural applications in point registration and localization, as well as connections to manifold learning.