;Steven J. Gortler;Craig Gotsman;Ligang Liu;Dylan P. Thurston
canadian journal of infectious diseases and medical microbiology2013Vol. 4pp. -
158
gortler2013journalon
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.