In the mathematical theory of structural rigidity, the Cayley configuration space of a linkage over a set of its non-edges , called Cayley parameters, is the set of distances attained by over all its frameworks, under some -norm. In other words, each framework of the linkage prescribes a unique set of distances to the non-edges of , so the set of all frameworks can be described by the set of distances attained by any subset of these non-edges. Note that this description may not be a bijection. The motivation for using distance parameters is to define a continuous quadratic branched covering from the configuration space of a linkage to a simpler, often convex, space. Hence, obtaining a framework from a Cayley configuration space of a linkage over some set of non-edges is often a matter of solving quadratic equations.
Cayley configuration spaces have a close relationship to the flattenability and combinatorial rigidity of graphs.
Definitions
Cayley configuration space Definition via linkages. Consider a linkage , with graph and -edge-length vector (i.e., -distances raised to the power, for some -norm) and a set of non-edges of . The Cayley configuration space of over in under the for some -norm, denoted by , is the set of -distance vectors attained by the non-edges over all frameworks of in . In the presence of inequality -distance constraints, i.e., an interval , the Cayley configuration space is defined analogously. In other words, is the projection of the Cayley-Menger semialgebraic set, with fixed or , onto the non-edges , called the Cayley parameters.
Definition via projections of the distance cone. Consider the cone of vectors of pairwise -distances between points. Also consider the -stratum of this cone , i.e., the subset of vectors of -distances between points in . For any graph , consider the projection of onto the edges of , i.e., the set of all vectors of -distances for which the linkage has a framework in . Next, for any point in and any set of non-edges of , consider the fiber of in along the coordinates of , i.e., the set of vectors of -distances for which the linkage has a framework in .
The Cayley configuration space is the projection of this fiber onto the set of non-edges , i.e., the set of -distances attained by the non-edges in over all frameworks of in . In the presence of inequality -distance constraints, i.e., an interval , the Cayley configuration space is the projection of a set of fibers onto the set of non-edges .
Definition via branching covers. A Cayley configuration space of a linkage in is the base space of a branching cover whose total space is the configuration space of the linkage in .
Oriented Cayley configuration space For a 1-dof tree-decomposable graph with base non-edge , each point of a framework of a linkage in under the -norm can be placed iteratively according to an orientation vector , also called a realization type. The entries of are local orientations of triples of points for all construction steps of the framework. A -oriented Cayley configuration space of over , denoted by is the Cayley configuration space of over restricted to frameworks respecting . In other words, for any value of in , corresponding of frameworks of respect and are a subset of the frameworks in .
Minimal complete Cayley vector For a 1-dof tree-decomposable graph with low Cayley complexity on a base non-edge , a minimal Cayley vector is a list of non-edges of such that the graph is generically globally rigid.
Properties
Single interval property A pair , consisting of a graph and a non-edge , has the single interval property in under some -norm if, for every linkage , the Cayley configuration space is a single interval.
Inherent convexity A graph has an inherent convex Cayley configuration space in under some norm if, for every partition of the edges of into and and every linkage , the Cayley configuration space is convex.
Genericity with respect to convexity Let be a graph and be a nonempty set of non-edges of . Also let be a framework in of any linkage whose constraint graph is and consider its corresponding -edge-length vector in the cone , where . As defined in Sitharam & Willoughby, the framework is generic with respect to the property of convex Cayley configuration spaces if
There is an open neighborhood of in the -stratum (corresponding to a neighborhood around of frameworks in ); and is convex if and only if, for all , is convex.
Theorem. Every generic framework of a graph in has a convex Cayley configuration space over a set of non-edges if and only if every linkage does.
Theorem. Convexity of Cayley configuration spaces is not a generic property of frameworks.
Proof. Consider the graph in Figure 1. Also consider the framework in whose pairwise -distance vector assigns distance 3 to the unlabeled edges, 4 to , and 1 to and the 2-dimensional framework whose pairwise -distance vector assigns distance 3 to the unlabeled edges, 4 to , and 4 to . The Cayley configuration space is 2 intervals: one interval represents frameworks with vertex on the right side of the line defined by vertices and and the other interval represents frameworks with vertex on the left side of this line. The intervals are disjoint due to the triangle inequalities induced by the distances assigned to the edges and . Furthermore, is a generic framework with respect to convex Cayley configuration spaces over in : there is a neighborhood of frameworks around whose Cayley configuration spaces are 2 intervals.
On the other hand, the Cayley configuration space is a single interval: the triangle-inequalities induced by the quadrilateral containing define a single interval that is contained in the interval defined by the triangle inequalities induced by the distances assigned to the edges and . Furthermore, is a generic framework with respect to convex Cayley configuration spaces over in : there is a neighborhood of frameworks around whose Cayley configuration spaces over in are a single interval. Thus, one generic framework has a convex Cayley configuration space while another does not.
Generic completeness A generically complete, or just complete, Cayley configuration space is a Cayley configuration of a linkage over a set of non-edges such that each point in this space generically corresponds to finitely many frameworks of and the space has full measure. Equivalently, the graph is generically minimally-rigid.
Results for the Euclidean norm The following results are for Cayley configuration spaces of linkages over non-edges under the -norm, also called the Euclidean norm.
Single interval theorems Let be a graph. Consider a 2-sum decomposition of , i.e., recursively decomposing into its 2-sum components. The minimal elements of this decomposition are called the minimal 2-sum components of .
Theorem. For , the pair , consisting of a graph and a non-edge , has the single interval property in if and only if all minimal 2-sum components of that contain are partial 2-trees.
The latter condition is equivalent to requiring that all minimal 2-sum components of that contain are 2-flattenable, as partial 2-trees are exactly the class of 2-flattenable graphs (see results on 2-flattenability). This result does not generalize for dimensions . The forbidden minors for 3-flattenability are the complete graph and the 1-skeleton of the octahedron (see results on 3-flattenability). Figure 2 shows counterexamples for . Denote the graph on the left by and the graph on the right by . Both pairs and have the single interval property in : the vertices of can rotate in 3-dimensions around a plane. Also, both and are themselves minimal 2-sum components containing . However, neither nor is 3-flattenable: contracting in yields and contracting in yields .
Example. Consider the graph in Figure 3 whose non-edges are and . The graph is its own and only minimal 2-sum component containing either non-edge. Additionally, the graph is a 2-tree, so is a partial 2-tree. Hence, by the theorem above both pairs and have the single interval property in .
The following conjecture characterizes pairs with the single interval property in for arbitrary .
Conjecture. The pair , consisting of a graph and a non-edge , has the single interval property in if and only if for any minimal 2-sum component of that contains and is not -flattenable, must be either removed, duplicated, or contracted to obtain a forbidden minor for -flattenability from .
1-dof tree-decomposable linkages in R2 The following results concern oriented Cayley configuration spaces of 1-dof tree-decomposable linkages over some base non-edge in . Refer to tree-decomposable graphs for the definition of generic linkages used below.
Theorem. For a generic 1-dof tree-decomposable linkage with base non-edge the following hold:
An oriented Cayley configuration space is a set of disjoint closed real intervals or empty; Any endpoint of these closed intervals corresponds to the length of in a framework of an extreme linkage; and For any vertex or any non-edge of , the maps from to the coordinates of or the length of in the frameworks of are continuous functions on each of these closed intervals.
This theorem yields an algorithm to compute (oriented) Cayley configuration spaces of 1-dof tree-decomposable linkages over a base non-edge by simply constructing oriented frameworks of all extreme linkages. This algorithm can take time exponential in the size of the linkage and in the output Cayley configuration space. For a 1-dof tree-decomposable graph , three complexity measures of its oriented Cayley configuration spaces are:
Cayley size: the maximum number of disjoint closed real intervals in the Cayley configuration space over all linkages ; Cayley computational complexity: the maximum time complexity to obtain these intervals over all linkages ; and Cayley algebraic complexity: the maximum algebraic complexity of describing each endpoint of these intervals over all linkages .
Bounds on these complexity measures are given in Sitharam, Wang & Gao. Another algorithm to compute these oriented Cayley configuration spaces achieves linear Cayley complexity in the size of the underlying graph.
Theorem. For a generic 1-dof tree-decomposable linkage , where the graph has low Cayley complexity on a base non-edge , the following hold:
There exist at most two continuous motion paths between any two frameworks of , and the time complexity to find such a path, if it exists, is linear in the number of interval endpoints of the oriented Cayley configuration space over that the path contains; and There is an algorithm that generates the entire set of connected components of the configuration space of frameworks of , and the time complexity of generating each such component is linear in the number of interval endpoints of the oriented Cayley configuration space over that the component contains.
An algorithm is given in Sitharam, Wang & Gao to find these motion paths. The idea is to start from one framework located in one interval of the Cayley configuration space, travel along the interval to its endpoint, and jump to another interval, repeating these last two steps until the target framework is reached. This algorithm utilizes the following facts: (i) there is a continuous motion path between any two frameworks in the same interval, (ii) extreme linkages only exist at the endpoints of an interval, and (iii) during the motion, the low Cayley complexity linkage only changes its realization type when jumping to a new interval and exactly one local orientation changes sign during this jump.