Positivity, Convexity and Computation in Rigidity Theory

Scientific Vision

Rigidity Theory studies the extent to which geometric objects are determined by partial combinatorial and metric data, either locally, globally, or up to certain transformations. The question of rigidity - in the form of local or global uniqueness - arises not only from modeling the physical world, but also naturally in a broad variety of abstract contexts. Modern rigidity theory therefore represents a general paradigm for solving certain classes of problems, and is well adapted to working with various discrete geometric objects such as bar-joint frameworks, polytopes, tensegrities, circle and sphere packings, weavings, piecewise-linear surfaces, etc. Several notions of rigidity are considered. For example, an objects is called locally rigid if it permits no continuous deformations that preserve the underlying constraints such as selected distances, angles or linear dependencies. In many cases, this amounts to %determining whether a given configuration is a the search and study of the real-isolated solutions of a system of polynomial equations, highlighting a strong connection between real algebraic geometry and rigidity theory.

Nowadays, rigidity theory has become outstandingly interdisciplinary, drawing from fields such as discrete, differential, convex and tropical geometry, as well as matroid theory, representation theory and spectral graph theory. In the context of this workshop we focus on three interlinked aspects of rigidity theory that have recently seen exciting developments and align strongly with the scope of the priority program SPP 2458 Combinatorial Synergies, namely positivity, convexity and computations.

Convexity refers to the study of geometric constraint systems derived from convex polytopes or contexts in which a notion of positive curvature can be defined. Assumptions of convexity are long-known to imply strong rigidity results, but the corresponding mechanisms are often surprisingly complex. Naturally, this connects to polytope theory, convex geometry and valuation theory.
Positivity refers to nonnegativity certificates for polynomials that naturally arise in many rigidity settings. These conditions come up, for example, for tensegrities, from the assumption of convexity, or whenever one employs second- and higher-order notions of rigidity. Here, there are strong connections to the field of positive and Lorentzian polynomials, and to real algebraic geometry in general.
Computation refers to the intrinsic need in rigidity theory for effective computational tools. Typically, small instances of interesting problems are already infeasibly large for analytical and symbolic approaches. This workshop focuses on applying numerical and symbolic techniques from polynomial optimization and real algebraic geometry to problems arising in the above contexts, as well as general approaches for dimensionality reduction.

The problems within this scope are highly interdisciplinary and call for close collaboration across different backgrounds.

Exemplary Problems

To better understand problems in rigidity theory that can potentially be tackled throughout this workshop, let us investigate two examples. First, consider the 1-skeleton of regular cube in $\mathbb{R}^3$ as a bar-joint framework. By coning $\mathcal{C}$, i.e. adding a vertex $v$ to $G$ alongside an edge to all previously present vertices $V$, we obtain the cone graph $G* \{v\}$. When adding a cone point to a framework, it is a priori unclear how its rigidity properties will change. Nevertheless, if the cone point lies on a convex polytope's interior, then the resulting framework is prestress stable. This begs the natural question what happens if the cone point lies outside of the polytope.

Prestress Stable Coned Cuboid — Figure 1: **(left)** Phase transition diagram induced by the rigidity behavior determined by the position of the cone point in $\mathbb{R}^3$. We distinguish rigid positions (red) from flexible positions (transparent). **(right)** The truncated icosahedron has a 5-dimensional space of nontrivial infinitesimal flexes when considered with edge length and facet planarity constraints. Still, it is rigid.

Truncated Icosahedron — Figure 1: **(left)** Phase transition diagram induced by the rigidity behavior determined by the position of the cone point in $\mathbb{R}^3$. We distinguish rigid positions (red) from flexible positions (transparent). **(right)** The truncated icosahedron has a 5-dimensional space of nontrivial infinitesimal flexes when considered with edge length and facet planarity constraints. Still, it is rigid.

In Figure 1l., we investigate the phase space associated with the framework. It turns out that the resulting framework is rigid, when the cone point exits the polytope's interior via an edge or a vertex. The rigid positions of the cone vertex are separated from the flexible positions by the prestress stability surface, which turns out to be algebraically highly complex and has the circumscribing sphere and the cube's hyperplanes as irreducible components. This experimental investigation combines topics from positivity, convexity and symmetry to simplify the complicated computational problem of deducing the coned framework's rigidity properties. I.e., the prestress stability test has been implemented as a SONC criterion for polynomial nonnegativity.

Furthermore, techniques from computational algebra can be used to show that the dodecahedron and the buckyball (see Figure 1r.) with edge length and facet planarity constraints are both second-order rigid, even though both possess a five-dimensional space of infinitesimal flexes and equilibrium stresses. So far, the approach relied on Gröbner bases and did not take into account the underlying real geometry, but instead relied on showing that in a certain polynomial system there is no nontrivial complex solution. Developing tools based on results from real algebraic geometry can yield improved certificates for the second-order rigidity of geometric constraint systems and may even produce a sufficient and necessary criterion.