Cayley configuration spaces of 2D mechanisms, Part I: extreme points, continuous motion paths and minimal representations

We consider longstanding questions concerning configuration spaces of 1-dof tree-decomposable linkages in 2D. By employing the notion Cayley configuration space, i.e., a set of intervals of realizable distance-values for an independent non-edge, we answer the following. (1) How to measure the complexity of the configuration space and efficiently compute that of low algebraic complexity? (2) How to restrict the Cayley configuration space to be a single interval? (3) How to efficiently obtain continuous motion paths between realizations? (4) How to bijectively represent of the Cartesian realization space as a curve in an ambient space of minimum dimension? (5) How robust is the complexity measure (1) and how to efficiently classify linkages according to it? In Part I of this paper, we deal with problems (1)-(4) by introducing the notions of (a) Cayley size, the number of intervals in the Cayley configuration space, (b) Cayley computational complexity of computing the interval endpoints, and (c) Cayley (algebraic) complexity of describing the interval endpoints. Specifically (i) We give an algorithm to find the interval endpoints of a Cayley configuration spac. For graphs with low Cayley complexity, we give the following. (ii) A natural, minimal set of local orientations, whose specification guarantees Cayley size of 1 and $O(|V|^2)$ Cayley computational complexity. Specifying fewer local orientations results in a superpolynomial blow-up of both Cayley size and computational complexity, provided P is different from NP. (iii) An algorithm--for generic linkages--to find a path of continuous motion (provided exists) between two given realizations, in time linear in a natural measure of path length. (iv) A canonical bijective representation of the Cartesian realization space in minimal ambient dimension, also for generic linkages.