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

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

Identifiers

  • HAL Id : hal-01229663, version 1

Collections

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. ⟨hal-01229663⟩

Share

Metrics

Record views

71

Files downloads

839