Service interruption on Monday 11 July from 12:30 to 13:00: all the sites of the CCSD (HAL, EpiSciences, SciencesConf, AureHAL) will be inaccessible (network hardware connection).
Skip to Main content Skip to Navigation
Conference papers

The combinatorics of CAT(0) cubical complexes

Abstract : Given a reconfigurable system $X$, such as a robot moving on a grid or a set of particles traversing a graph without colliding, the possible positions of $X$ naturally form a cubical complex $\mathcal{S}(X)$. When $\mathcal{S}(X)$ is a CAT(0) space, we can explicitly construct the shortest path between any two points, for any of the four most natural metrics: distance, time, number of moves, and number of steps of simultaneous moves. CAT(0) cubical complexes are in correspondence with posets with inconsistent pairs (PIPs), so we can prove that a state complex $\mathcal{S}(X)$ is CAT(0) by identifying the corresponding PIP. We illustrate this very general strategy with one known and one new example: Abrams and Ghrist's ``positive robotic arm" on a square grid, and the robotic arm in a strip. We then use the PIP as a combinatorial ``remote control" to move these robots efficiently from one position to another.
Document type :
Conference papers
Complete list of metadata

Cited literature [14 references]  Display  Hide  Download
Contributor : Alain Monteil Connect in order to contact the contributor
Submitted on : Tuesday, November 17, 2015 - 10:19:31 AM
Last modification on : Thursday, July 4, 2019 - 4:22:02 PM
Long-term archiving on: : Thursday, February 18, 2016 - 11:32:59 AM


Publisher files allowed on an open archive




Federico Ardila, Tia Baker, Rika yatchak. The combinatorics of CAT(0) cubical complexes. 25th International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2013), 2013, Paris, France. pp.849-860, ⟨10.46298/dmtcs.2348⟩. ⟨hal-01229663⟩



Record views


Files downloads