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

How hard is it to program <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="n"> <mml:semantics> <mml:mi>n</mml:mi> <mml:annotation encoding="application/x-tex">n</mml:annotation> </mml:semantics> </mml:math> </inline-formula> robots to move about a long narrow aisle such that only <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="w"> <mml:semantics> <mml:mi>w</mml:mi> <mml:annotation encoding="application/x-tex">w</mml:annotation> </mml:semantics> </mml:math> </inline-formula> of them can fit across the width of the aisle? In this paper, we answer that question by calculating the topological complexity of <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="c o n f left-parenthesis n comma w right-parenthesis"> <mml:semantics> <mml:mrow> <mml:mi>conf</mml:mi> <mml:mo>⁡</mml:mo> <mml:mo stretchy="false">(</mml:mo> <mml:mi>n</mml:mi> <mml:mo>,</mml:mo> <mml:mi>w</mml:mi> <mml:mo stretchy="false">)</mml:mo> </mml:mrow> <mml:annotation encoding="application/x-tex">\operatorname {conf}(n,w)</mml:annotation> </mml:semantics> </mml:math> </inline-formula>, the ordered configuration space of <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="n"> <mml:semantics> <mml:mi>n</mml:mi> <mml:annotation encoding="application/x-tex">n</mml:annotation> </mml:semantics> </mml:math> </inline-formula> open unit-diameter disks in the infinite strip of width <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="w"> <mml:semantics> <mml:mi>w</mml:mi> <mml:annotation encoding="application/x-tex">w</mml:annotation> </mml:semantics> </mml:math> </inline-formula>. By studying its cohomology ring, we prove that, as long as <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="n"> <mml:semantics> <mml:mi>n</mml:mi> <mml:annotation encoding="application/x-tex">n</mml:annotation> </mml:semantics> </mml:math> </inline-formula> is greater than <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="w"> <mml:semantics> <mml:mi>w</mml:mi> <mml:annotation encoding="application/x-tex">w</mml:annotation> </mml:semantics> </mml:math> </inline-formula>, the topological complexity of <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="c o n f left-parenthesis n comma w right-parenthesis"> <mml:semantics> <mml:mrow> <mml:mi>conf</mml:mi> <mml:mo>⁡</mml:mo> <mml:mo stretchy="false">(</mml:mo> <mml:mi>n</mml:mi> <mml:mo>,</mml:mo> <mml:mi>w</mml:mi> <mml:mo stretchy="false">)</mml:mo> </mml:mrow> <mml:annotation encoding="application/x-tex">\operatorname {conf}(n,w)</mml:annotation> </mml:semantics> </mml:math> </inline-formula> is <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="2 n minus 2 left ceiling StartFraction n Over w EndFraction right ceiling plus 1"> <mml:semantics> <mml:mrow> <mml:mn>2</mml:mn> <mml:mi>n</mml:mi> <mml:mo>−</mml:mo> <mml:mn>2</mml:mn> <mml:mstyle scriptlevel="0"> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mo maxsize="1.2em" minsize="1.2em">⌈</mml:mo> </mml:mrow> </mml:mstyle> <mml:mfrac> <mml:mi>n</mml:mi> <mml:mi>w</mml:mi> </mml:mfrac> <mml:mstyle scriptlevel="0"> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mo maxsize="1.2em" minsize="1.2em">⌉</mml:mo> </mml:mrow> </mml:mstyle> <mml:mo>+</mml:mo> <mml:mn>1</mml:mn> </mml:mrow> <mml:annotation encoding="application/x-tex">2n-2\big \lceil \frac {n}{w}\big \rceil +1</mml:annotation> </mml:semantics> </mml:math> </inline-formula>, providing a lower bound for the minimum number of cases such a program must consider.