2024/04/17 by Nicholas Wawrykow, Wawrykow, Nicholas · 1 citation
Computer Science · Mathematics · #55R80 #57Z20 #Algebraic Topology (math.AT) #Computational Geometry and Mesh Generation #Differential Geometry (math.DG) #FOS: Mathematics #Geometric and Algebraic Topology #Mathematical Dynamics and Fractals
paper · pdf · doi:10.48550/arxiv.2404.11711
openalex publication_date 2024/04/17 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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 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 conf(n,w) is 2n-2\lceil(n)/(w)\rceil+1, providing a lower bound for the minimum number of cases such a program must consider.