Combinatorial genericity and minimal rigidity
Ileana Streinu, Louis Theran · 2008
A well studied geometric problem, with applications ranging from molecular structure determination to sensor networks, asks for the reconstruction of a set P of n unknown points from a finite set of pairwise distances (up to Euclidean isometries). We are concerned here with a related problem: which sets of distances are minimal with the property that they allow for the reconstruction of P, up to a finite set of possibilities? In the planar case, the answer is known generically via the landmark Maxwell-Laman Theorem from Rigidity Theory, and it leads to a combinatorial answer: the underlying structure of such a generic minimal collection of distances is a minimally rigid (or Laman) graph, for which very efficient combinatorial decision algorithms exist. For non-generic cases the situation appears to be dramatically different, with the best known algorithms relying on exponential-time Gröbner base methods, and some specific instances known to be NP-hard. Understanding what makes a point set generic emerges as an intriguing geometric question with practical algorithmic consequences.