Cayley configuration space
In mathematics, the Cayley configuration space of a linkage over a set of its non-edges formula_1, called Cayley parameters, is the set of distances attained by formula_1 over all its frameworks, under some formula_3-norm. In other words, each framework of the linkage prescribes a unique set of distances to the non-edges of formula_4, 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 formula_5, with graph formula_4 and formula_7-edge-length vector formula_8 (i.e., formula_3-distances raised to the formula_10 power, for some formula_3-norm) and a set of non-edges formula_1 of formula_4. The  Cayley configuration space of formula_5 over formula_1 in formula_16 under the for some formula_3-norm, denoted by formula_18, is the set of formula_7-distance vectors formula_20 attained by the non-edges formula_1 over all frameworks of formula_5 in formula_16. In the presence of inequality formula_7-distance constraints, i.e., an interval formula_25, the Cayley configuration space formula_26 is defined analogously. In other words, formula_18 is the projection of the Cayley-Menger semialgebraic set, with fixed formula_5 or formula_29, onto the non-edges formula_1, called the Cayley parameters. Definition via projections of the distance cone. Consider the cone formula_31 of vectors of  pairwise formula_7-distances between formula_33 points. Also consider the formula_34-stratum of this cone formula_35, i.e., the subset of vectors of formula_7-distances between formula_33 points in formula_16. For any graph formula_4, consider the projection formula_40 of formula_35 onto the edges of formula_4, i.e., the set of all vectors formula_43 of formula_7-distances for which the linkage formula_45 has a framework in formula_16. Next, for any point formula_43 in formula_40 and any set of non-edges formula_1 of formula_4, consider the fiber of formula_43 in formula_35 along the coordinates of formula_1, i.e., the set of vectors formula_54 of formula_7-distances  for which the linkage formula_56 has a framework in formula_16. The Cayley configuration space formula_18 is the projection of this fiber onto the set of non-edges formula_1, i.e., the set of formula_7-distances attained by the non-edges in formula_1 over all frameworks of formula_45 in formula_16. In the presence of inequality formula_7-distance constraints, i.e., an interval formula_65, the Cayley configuration space formula_66 is the projection of a set of fibers onto the set of non-edges formula_1. Definition via branching covers. A Cayley configuration space of a linkage in formula_16 is the base space of a branching  cover whose total space is the configuration space of the linkage in formula_16. Oriented Cayley Configuration Space. For a formula_70-dof tree-decomposable graph formula_4 with base non-edge formula_72, each point of a framework of a linkage formula_5 in formula_16 under the formula_75-norm can be placed iteratively according to an orientation vector formula_76, also called a realization type. The entries of formula_76 are local orientations of triples of points for all construction steps of the framework. A formula_76-oriented Cayley configuration space of formula_5 over formula_72, denoted by formula_81 is the Cayley configuration space of formula_5 over formula_72  restricted to frameworks respecting formula_76. In other words, for any value of formula_72 in formula_81, corresponding of frameworks of formula_5 respect formula_76 and are a subset of the frameworks in formula_89. Minimal complete Cayley vector. For a formula_70-dof tree-decomposable graph formula_91 with low Cayley complexity on a base non-edge formula_72, a minimal Cayley vector formula_1 is a list of formula_94 non-edges of formula_4 such that the graph formula_96 is generically globally rigid. Properties. Single Interval Property.. A pair formula_97, consisting of a graph formula_4 and a non-edge formula_72, has the single interval property in formula_16  under some formula_3-norm if, for every linkage formula_5, the Cayley configuration space formula_103 is a single interval. Inherent Convexity. A graph formula_4 has an inherent convex Cayley configuration space in formula_16 under some formula_3 norm if, for every partition of the edges of formula_4 into formula_108 and formula_1 and every linkage formula_110, the Cayley configuration space formula_111 is convex. Genericity with respect to convexity. Let formula_112 be a graph and formula_1 be a nonempty set of non-edges of formula_4. Also let formula_115 be a framework in formula_16 of any linkage whose constraint graph is formula_4 and consider its  corresponding formula_7-edge-length vector formula_119 in the cone formula_31, where formula_121. As defined in, the framework formula_115 is generic with respect to the property of convex Cayley configuration spaces if Theorem. Every generic framework of a graph formula_4 in formula_16 has a convex Cayley configuration space over a set of non-edges formula_1 if and only if every linkage formula_5 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 formula_136 in formula_137 whose pairwise formula_75-distance vector formula_139 assigns distance formula_140 to the  unlabeled edges, formula_141 to formula_142, and formula_70 to formula_144 and the formula_145-dimensional framework formula_146 whose pairwise formula_75-distance vector formula_148 assigns distance formula_140 to the unlabeled edges, formula_141 to formula_142, and formula_141 to formula_144. The Cayley configuration space formula_154 is formula_145 intervals: one interval represents frameworks with vertex formula_156 on the right side of the line defined by vertices formula_157 and formula_158 and the other interval represents frameworks with vertex formula_156 on the left side of this line. The intervals are disjoint due to the triangle inequalities induced by the distances assigned to the edges formula_142 and formula_144. Furthermore , formula_136 is a generic framework with respect to convex Cayley configuration spaces over formula_72 in formula_137: there is a neighborhood of frameworks around formula_136 whose Cayley configuration spaces formula_166 are formula_145 intervals. On the other hand, the Cayley configuration space formula_168 is a single interval: the triangle-inequalities induced by the quadrilateral containing formula_72 define a single interval that is contained in the interval defined by the triangle inequalities induced by the distances assigned to the edges formula_142 and formula_144. Furthermore, formula_146 is a generic framework with respect to convex Cayley configuration spaces over formula_72 in formula_137: there is a  neighborhood of frameworks around formula_146 whose Cayley configuration spaces over formula_72 in formula_137 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 formula_5 over a set of non-edges formula_1 such that each point in this space generically corresponds to finitely many frameworks of formula_5 and the space has full measure. Equivalently, the graph formula_96 is generically minimally-rigid. = Results for the Euclidean norm = This sections gives results on Cayley configuration  spaces of linkages over non-edges under the formula_75-norm, also called the Euclidean norm. Single Interval Theorems. Let formula_4 be a graph. Consider a formula_145-sum decomposition of formula_4, i.e., recursively decomposing formula_4 into its formula_145-sum components. The minimal elements of this decomposition are called the minimal formula_145-sum components of formula_4. Theorem. For formula_190, the pair formula_97, consisting of a graph formula_4 and a non-edge formula_72, has the single interval property in formula_16 if and only if all minimal formula_145-sum components of formula_196 that contain formula_72 are partial formula_145-trees. The latter condition is equivalent  to requiring that all minimal formula_145-sum components of formula_196 that contain formula_72 are formula_145-flattenable, as partial formula_145-trees are exactly the class of formula_145-flattenable graphs (see results on formula_145-flattenability). This result does not generalize for dimensions formula_206. The forbidden minors for formula_140-flattenability are the complete graph formula_208 and the formula_70-skeleton of the octahedron formula_210 (see results on formula_140-flattenability). Figure 2 shows counterexamples for formula_212. Denote the graph on the left by formula_4 and the graph on the right by formula_108. Both pairs formula_97 and formula_216 have the single interval property in formula_217: the  vertices of formula_72 can rotate in formula_140-dimensions around a plane. Also, both formula_196 and formula_221 are themselves minimal formula_145-sum components containing formula_72. However, neither formula_196 nor formula_221 is formula_140-flattenable: contracting formula_72 in formula_196 yields formula_208 and contracting formula_72 in formula_221 yields formula_210. Example. Consider the graph formula_4 in Figure 3 whose non-edges are formula_234 and formula_235. The graph formula_4 is its own and only minimal formula_145-sum component containing either non-edge. Additionally, the graph formula_238 is a formula_145-tree, so formula_4 is a partial formula_145-tree. Hence, by the theorem above both pairs formula_242 and  formula_243 have the single interval property in formula_137. The following conjecture characterizes pairs formula_97 with the single interval property in formula_16 for arbitrary formula_34. Conjecture. The pair formula_97, consisting of a graph formula_4 and a non-edge formula_72, has the single interval property in formula_16 if and only if for any minimal formula_145-sum component of formula_196 that contains formula_72 and is not formula_34-flattenable, formula_72 must be either removed, duplicated, or contracted to obtain a forbidden minor for formula_34-flattenability from formula_4. Section::::"1"-dof tree-decomposable linkages in formula_137. The following results concern oriented Cayley configuration spaces of 1-dof  tree-decomposable linkages over some base non-edge in formula_137. Refer to tree-decomposable graphs for the definition of generic linkages used below. Theorem. For a generic 1-dof tree-decomposable linkage formula_5 with base non-edge formula_72 the following hold: 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, see constructing a tree-decomposable framework. 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 formula_4, three complexity measures of its oriented Cayley configuration spaces are: Bounds on these complexity measures are given in. See results on tree-decomposable graphs. 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 formula_5, where the graph formula_4 has low Cayley complexity on a base non-edge formula_72, the following hold: An algorithm is given in 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. Example. Figure 4 shows an oriented framework of a 1-dof  tree-decomposable linkage with base non-edge formula_283, located in an interval of the Cayley configuration space, and two other frameworks whose orientations are about to change. The vertices corresponding to construction steps are labelled in order of construction. More specifically, the first framework has the realization type formula_284. There is a continuous motion path to the second framework, which has the realization type formula_285. Hence, this framework corresponds to an interval endpoint and jumping to a new interval results in the realization type formula_286. Likewise, the third framework is corresponds to an interval endpoint with the realization type formula_287  and jumping to a new interval results in the realization type formula_288. Theorem. (1) For a generic formula_70-path, 1-dof tree-decomposable linkage formula_5 with low Cayley complexity, there exists a bijective correspondence between the set of frameworks of formula_5 and points on a formula_145-dimensional curve, whose points are the minimum complete Cayley distance vectors. (2) For a generic 1-dof tree-decomposable linkage formula_5 with low Cayley complexity, there exists a bijective correspondence between the set of frameworks of formula_5 and points on an formula_33-dimensional curve, whose points are the minimum complete Cayley distance vectors, where  formula_33 is the number of last level vertices of the graph formula_4. = Results for general "p"-norms = This section covers the results that can be extended to general formula_3-norms. Theorem. For general formula_3-norms, a graph formula_4 has a inherent convex Cayley configuration space in formula_16 if and only if formula_4 is formula_34-flattenable. The "only if" direction was proved in using the fact that the formula_304 distance cone formula_305 is convex. As a direct consequence, formula_34-flattenable graphs and graphs with inherent convex Cayley configuration spaces in formula_16 have the same forbidden minor characterization. See Graph Flattenability  for results on these characterizations, as well as a more detailed discussion on the connection between Cayley configuration spaces and flattenability. Example. Consider the graph in Figure 3 with both non-edges added as edges. The resulting graph is a formula_145-tree, which is formula_145-flattenable under the formula_310 and formula_75 norms, see Graph Flattenability. Hence, the theorem above indicates that the graph has a inherent convex Cayley configuration space in formula_137 under the formula_310 and formula_75 norms. In particular, the Cayley configuration space over one or both of the non-edges formula_234 and formula_235 is convex. Applications. The EASAL  algorithm makes use of the techniques developed in for dealing with convex Cayley configuration spaces to describe the dimensional, topological, and geometric structure of Euclidean configuration spaces in formula_217. More precisely, for two sets of formula_33 points formula_319 and formula_156 in formula_217 with interval distance constraints between pairs of points coming from different sets, EASAL outputs all the frameworks of this linkage such that no pair of constrained points is too close together and at least one pair of constrained points is sufficiently close together. This algorithm has applications in molecular self-assembly.