Two robots moving geodesically on a tree

Abstract

We study the geodesic complexity of the ordered and unordered configuration spaces of graphs in both the ${\ell }_1$ and ${\ell }_2$ metrics. We determine the geodesic complexity of the ordered two-point $\epsilon$-configuration space of any star graph in both the ${\ell }_1$ and ${\ell }_2$ metrics and of the unordered two-point configuration space of any tree in the ${\ell }_1$ metric, by finding explicit geodesics from any pair to any other pair, and arranging them into a minimal number of continuously-varying families. In each case the geodesic complexity matches the known value of the topological complexity.

20 pages, 17 figures