The topological complexity of the ordered configuration space of disks in a strip

Abstract

How hard is it to program $n$ robots to move about a long narrow aisle such that only $w$ of them can fit across the width of the aisle? In this paper, we answer that question by calculating the topological complexity of $\text{conf}(n,w)$, the ordered configuration space of open unit-diameter disks in the infinite strip of width $w$. By studying its cohomology ring, we prove that, as long as $n$ is greater than $w$, the topological complexity of $\text{conf}(n,w)$ is $2n-2\lceil \frac{n}{w}\rceil +1$, providing a lower bound for the minimum number of cases such a program must consider.

9 pages, 3 figures