The graph rigidity problem in arbitrary dimension

点击翻译按钮获取中文摘要

Graph rigidity is an interdisciplinary field which aims to provide techniques for identifying rigidity and flexibility properties of discrete geometric structures. The structures may be thought of as assemblies of rigid building blocks with connecting joints and are generally categorised by the nature of these blocks and joints; e.g. bar-and-joint, body-and-bar and panel and-hinge frameworks. Constraint systems of these forms are ubiquitous in nature (e.g. periodic structures in proteins, symmetry in virus capsids and the analysis of materials), in engineering (e.g. tensegrities, trusses, linkages and deployable structures) and in technology (e.g. formation control for multi-agent systems, sensor network localisation, machine learning and CAD).As a simple example, consider a triangle and a square. A triangle is rigid: its angles are determined by the lengths of its edges. A square is flexible: you can deform it into a diamond-shape without changing the lengths of its edges. In general, given a structure and a constraint system modelled on the underling graph of the structure, the defining questions of the area are whether: the structure is unique (global rigidity); there are a finite number of realisations satisfying the given constraints (rigidity); or there are infinitely many realisations (flexibility). Graph rigidity may be traced back to the 18th century and the conjectures of Cauchy and Euler that triangulated structures, such as geodesic domes, which have rigid bars connected together at their endpoints by universal joints, are inherently rigid. While Cauchy obtained a proof in the convex case, subsequent work extending his theorem continued until Connelly demonstrated the existence of flexible polyhedra in the 1970s.The combinatorial focus of graph rigidity can be traced to James Clerk Maxwell who, in 1864, developed necessary counting conditions on the underlying graph for bar-joint structures to be rigid. In general determining when a structure is rigid is NP-hard, i.e. it belongs to a family of problems for which it is widely believed there is no efficient solution. However, generically (in the sense of algebraic geometry), rigidity and global rigidity can be expressed as linear algebraic properties (on a Jacobean matrix and a weighted Laplacian matrix respectively), and then attacked by interweaving the theory of matroids and sparse graphs with geometric techniques. Matroids were introduced as a mathematical structure by Whitney in the 1930s. They extend the notion of linear independence of a set of vectors and have numerous important applications in Operational Research and Combinatorial Optimisation.In 1920 Polaczek-Geiringer proved that Maxwell's conditions are sufficient to characterise 2-dimensional generic rigidity and crucially this leads quickly to fast deterministic graph orientation algorithms for rigidity testing. However in higher dimensions Maxwell's conditions do not suffice and the d-dimensional graph rigidity problem (finding such a characterisation and showing a resulting fast algorithm) remains a crucial open problem of wide potential applicability.The main aim of the project is to deploy a novel approach in order to resolve the graph rigidity problem. The project will extend foundational results in matroid theory and utilise intricate sparse graph techniques. These tools will then be exploited alongside a very recent strengthening of a classical dimension hopping principle from projective geometry. The techniques should result in ground-breaking combinatorial descriptions of when a generic bar-joint structure is rigid or flexible. It will then be of fundamental importance, in a future large project, to investigate the extent to which the descriptions can be tested by fast deterministic algorithms. Given the wide ranging applications, it will also be crucial to implement the algorithms alongside existing software packages such as ProFlex and KINARI.