Paper detail

A Class of Minimal Generically Universally Rigid Frameworks

Following a review of related results in rigidity theory, we provide a construction to obtain generically universally rigid frameworks with the minimum number of edges, for any given set of n nodes in two or three dimensions. When a set of edge-lengths is compatible with only one configuration in d-dimensions, the framework is globally rigid. When that configuration is unique even if embedded in a higher dimensional space, the framework is universally rigid. In case of generic configurations, where the nodal coordinates are algebraically independent, the minimum number of edges required is equal to dn-d(d+1)/2+1, that is, 2n-2 for d=2, and 3n-5 for d=3. Our contribution is a specific construction for this case by introducing a class of frameworks generalizing that of Grünbaum polygons. The construction applies also to nongeneric configurations, although in this case the number of edges is not necessarily the minimum. One straightforward application is the design of wireless sensor networks or multi-agent systems with the minimum number of communication links.