On affine rigidity

Steven J. Gortler, Craig Gotsman, Ligang Liu, Dylan P. Thurston


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.

Full Text:


DOI: http://dx.doi.org/10.20382/jocg.v4i1a7

ISSN: 1920-180X