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).

# 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.
Keywords :
Document type :
Conference papers

Cited literature [14 references]

https://hal.inria.fr/hal-01229663
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

### File

dmAS0172.pdf
Publisher files allowed on an open archive

### Citation

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