Simplicial complexity: piecewise linear motion planning in robotics (Q1743761): Difference between revisions

Let \(X\) be a topological space, \(P(X)\) the free path space of \(X\). The topological complexity of \(X\), denoted \(\mathrm{TC}(X)\), is the cardinality of the least integer \(n\) such that there exists a cover \(\{U_i\}_{i=0}^n\) of \(X\times X\) so that the map \(e: P(X)\to X \times X\) admits a section \(\sigma_i\) on each \(U_i\). Here \(e(\gamma):=(\gamma(0), \gamma(1))\). This homotopy invariant is notoriously difficult to compute. Generally, an optimal covering is constructed to obtain an upper bound on for \(\mathrm{TC}(X)\) while a lower bound can be given by considering homotopical or cohomological obstructions. The paper under review seeks to make the process easier by utilizing ideas in combinatorial topology. The author develops a definition of topological complexity, called \textbf{simplicial complexity} and denoted \(\mathrm{SC}\), for an abstract ordered simplicial complex, an ordering which is needed to be able to define products of simplicial complexes. Note that the simplicial complexity is distinct from the discrete topological complexity of \textit{D. Fernández-Ternero} et al. [Proc. Am. Math. Soc. 146, No. 10, 4535--4548 (2018; Zbl 1402.55007)]. The main contribution of this paper is that if \(K\) is a finite simplicial complex, then the simplicial complexity of the simplicial complex \(K\) is equal to the topological complexity of the geometric realization of \(K\). Thus, the question of computing \(\mathrm{TC}(X)\) is recast into the question of finding a simplicial complex \(K\) whose geometric realization is homotopy equivalent to \(X\), and then computing the simplicial complexity of \(K\). The notion of contiguity between two simplicial maps \(f: K \to L\) between simplicial complexes plays an analogous role to that of homotopy between topological spaces. Recall that simplicial maps \(f,g: K\to L\) are contiguous if whenever \(\sigma\) is a simplex of \(K\), then \(f(\sigma)\cup g(\sigma)\) is a simplex of \(L\). The author then introduces the notion of a \(c\)-contiguity where two maps \(f,g: K\to L\) are \(c\)-contiguous if there is a sequence of maps \(f=f_0,f_1, \ldots , f_c=g: K \to L\) with \(f_{i-1}\) and \(f_i\) contiguous. The simplicial complexity also heavily utilizes approximation results. Let \(\mathrm{Sd}^b(K)\) denote the \(b^{th}\) barycentric subdivision of \(K\). The \((b,c)\)-simplicial complexity of an ordered complex \(K\) is one less than the smallest cardinality of finite covers of \(\mathrm{Sd}^b(K\times K)\) by subcomplexes \(J\) such that the compositions \[ J \hookrightarrow \mathrm{Sd}^b(K\times K)\stackrel{\pi_1}\to K \text{ and } J \hookrightarrow \mathrm{Sd}^b(K\times K)\stackrel{\pi_2}\to K \] are \(c\)-contiguous. As the value of \(c\) increases, the \((b,c)\)-simplicial complexity weakly decreases, and the author shows that this value eventually stabilizes. The value to which it stabilizes is then defined to be the simplicial complexity of \(K\). The author goes on to show that this value agrees with the topological complexity of the geometric realization. The final section of the paper is devoted to illustrating the use of the new technique by explicitly computing the topological complexity of the circle \(S^1\). This is equivalent to computing the simplicial complexity of the \(1\)-skeleton of the \(\Delta^2\). Although the topological complexity of the circle has been known since Farber, the purpose of this section, as pointed out by the author, is to motivate and encourage development of algorithmic implementations of the work found in the paper, as well as to provide a ``benchmark'' for testing and comparing implementations. In that sense, there seems to be great promise and potential for future work based on these ideas.