Cayley configuration space

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

edit

Cayley configuration space

edit

Definition via linkages.[1] 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.[2] 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  .[2] 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

edit

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  .[3] 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

edit

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.[4][5]

Properties

edit

Single interval property

edit

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.[1]

Inherent convexity

edit

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.[1]

Genericity with respect to convexity

edit

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,[2] 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.[2] 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.

 
Figure 1. A graph   with a non-edge  . There exist two frameworks in   under the  -norm that are generic with respect to convex Cayley configuration spaces over   such that the distances attained by   form a single interval for one framework but not for the other.

Theorem.[2] 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

edit

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.[1] Equivalently, the graph   is generically minimally-rigid.[1]

Results for the Euclidean norm

edit

The following results are for Cayley configuration spaces of linkages over non-edges under the  -norm, also called the Euclidean norm.

Single interval theorems

edit
 
Figure 2. The graphs and their non-edges   each has the single interval property in  . Both graphs with   added as an edge are their own minimal 2-sum components that contain  , but neither is 3-flattenable.

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.[1] 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  .[1] 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  .

 
Figure 3. The graph   shown left. For the linkage   that assigns the distance 1 to the edges of  , the Cayley configuration space   is shown right.

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.[1] 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

edit

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.[3] 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.[3][4] 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:[4]

  • 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.[4][5] Another algorithm to compute these oriented Cayley configuration spaces achieves linear Cayley complexity in the size of the underlying graph.[4]

Theorem.[4][6] 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[4] 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.

 
Figure 4. Three oriented frameworks, with base non-edge  , along a continuous motion path. The last two frameworks are about to change orientations.

Example. Figure 4 shows an oriented framework of a 1-dof tree-decomposable linkage with base non-edge  , 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  . There is a continuous motion path to the second framework, which has the realization type  . Hence, this framework corresponds to an interval endpoint and jumping to a new interval results in the realization type  . Likewise, the third framework is corresponds to an interval endpoint with the realization type   and jumping to a new interval results in the realization type  .

Theorem.[4][6] (1) For a generic 1-path, 1-dof tree-decomposable linkage   with low Cayley complexity, there exists a bijective correspondence between the set of frameworks of   and points on a 2-dimensional curve, whose points are the minimum complete Cayley distance vectors. (2) For a generic 1-dof tree-decomposable linkage   with low Cayley complexity, there exists a bijective correspondence between the set of frameworks of   and points on an  -dimensional curve, whose points are the minimum complete Cayley distance vectors, where   is the number of last level vertices of the graph  .

Results for general p-norms

edit

These results are extended to general  -norms.

Theorem.[2] For general  -norms, a graph   has an inherent convex Cayley configuration space in   if and only if   is  -flattenable.

The "only if" direction was proved in Sitharam & Gao[1] using the fact that the   distance cone   is convex. As a direct consequence,  -flattenable graphs and graphs with inherent convex Cayley configuration spaces in   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 2-tree, which is 2-flattenable under the   and   norms, see Graph flattenability. Hence, the theorem above indicates that the graph has an inherent convex Cayley configuration space in   under the   and   norms. In particular, the Cayley configuration space over one or both of the non-edges   and   is convex.

Applications

edit

The EASAL algorithm[7] makes use of the techniques developed in Sitharam & Gao[1] for dealing with convex Cayley configuration spaces to describe the dimensional, topological, and geometric structure of Euclidean configuration spaces in  . More precisely, for two sets of   points   and   in   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.

References

edit
  1. ^ a b c d e f g h i j Sitharam, Meera; Gao, Heping (2010-04-01). "Characterizing Graphs with Convex and Connected Cayley Configuration Spaces". Discrete & Computational Geometry. 43 (3): 594–625. doi:10.1007/s00454-009-9160-8. ISSN 1432-0444. S2CID 35819450.
  2. ^ a b c d e f Sitharam, Meera; Willoughby, Joel (2015). Botana, Francisco; Quaresma, Pedro (eds.). "On Flattenability of Graphs". Automated Deduction in Geometry. Lecture Notes in Computer Science. 9201. Cham: Springer International Publishing: 129–148. arXiv:1503.01489. doi:10.1007/978-3-319-21362-0_9. ISBN 978-3-319-21362-0. S2CID 23208.
  3. ^ a b c Gao, Heping; Sitharam, Meera (2009-03-08). "Characterizing 1-dof Henneberg-I graphs with efficient configuration spaces". Proceedings of the 2009 ACM symposium on Applied Computing. SAC '09. Honolulu, Hawaii: Association for Computing Machinery. pp. 1122–1126. doi:10.1145/1529282.1529529. ISBN 978-1-60558-166-8. S2CID 14117144.
  4. ^ a b c d e f g h Sitharam, Meera; Wang, Menghan; Gao, Heping (2011). "Cayley configuration spaces of 2D mechanisms, Part I: extreme points, continuous motion paths and minimal representations". Preprint. arXiv:1112.6008.
  5. ^ a b Sitharam, Meera; Wang, Menghan; Gao, Heping (2011). "Cayley Configuration Spaces of 1-dof Tree-decomposable Linkages, Part II: Combinatorial Characterization of Complexity". Preprint. arXiv:1112.6009.
  6. ^ a b Sitharam, Meera; Wang, Menghan (2014-01-01). "How the Beast really moves: Cayley analysis of mechanism realization spaces using CayMos". Computer-Aided Design. 46: 205–210. doi:10.1016/j.cad.2013.08.033. ISSN 0010-4485.
  7. ^ Ozkan, Aysegul; Prabhu, Rahul; Baker, Troy; Pence, James; Peters, Jorg; Sitharam, Meera (2018-07-26). "Algorithm 990: Efficient Atlasing and Search of Configuration Spaces of Point-Sets Constrained by Distance Intervals". ACM Transactions on Mathematical Software. 44 (4): 48:1–48:30. doi:10.1145/3204472. ISSN 0098-3500. S2CID 29156131.