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

How hard is it to program



n
n



robots to move about a long narrow aisle such that only



w
w



of them can fit across the width of the aisle? In this paper, we answer that question by calculating the topological complexity of




conf

⁡


(
n
,
w
)

\operatorname {conf}(n,w)



, the ordered configuration space of



n
n



open unit-diameter disks in the infinite strip of width



w
w



. By studying its cohomology ring, we prove that, as long as



n
n



is greater than



w
w



, the topological complexity of




conf

⁡


(
n
,
w
)

\operatorname {conf}(n,w)



is




2
n

−


2


⌈



n
w



⌉


+
1

2n-2\big \lceil \frac {n}{w}\big \rceil +1



, providing a lower bound for the minimum number of cases such a program must consider.