Topological complexity and efficiency of motion planning algorithms (Q1725561): Difference between revisions

In this paper, the authors introduce a variant of Farber's topological complexity $TC(X)$ when $X$ is a smooth compact Riemannian manifold. To this end, they first notice that, for such spaces, $TC(X)$ is obtained by requiring that domains of continuity of any motion planner $\sigma :X\times X\rightarrow X^I$ (a section of the path fibration $\pi : X^I\rightarrow X\times X$) are mutually disjoint locally compact subsets recovering $X\times X$. This enables them to define the length of $\sigma $ by putting: \[ l(\sigma):=\int_{X\times X}l\circ \sigma. \] Here, the length $l(\alpha)$ is understood in the metric sense for paths $\alpha \in X^I$ which are merely continuous [\textit{P. Petersen}, Riemannian geometry. 2nd ed. New York, NY: Springer (2006; Zbl 1220.53002)]. A motion planner is then called \textit{efficient} if $l(\sigma)=\int_{X\times X}d$. The introduced variant, denoted $lTC(X)$ and called \textit{efficient topological complexity} is, by definition, the minimal integer $m\geq 0$ such that there exists an efficient motion planner $\sigma $ having exactly $m+1$ domains of continuity. \par The main result of the paper is stated as follows: \par Theorem 1: If $X$ is a smooth closed Riemannian manifold, then \[ TC(X)\leq lTC(X)\leq TC(X)+1. \] At the end, an example is presented showing that when $X$ has a non-empty boundary, Theorem 1 does not apply.