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.
Type de document :
Communication dans un congrès
Alain Goupil and Gilles Schaeffer. 25th International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2013), 2013, Paris, France. Discrete Mathematics and Theoretical Computer Science, DMTCS Proceedings vol. AS, 25th International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2013), pp.849-860, 2013, DMTCS Proceedings
Liste complète des métadonnées

Littérature citée [14 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-01229663
Contributeur : Alain Monteil <>
Soumis le : mardi 17 novembre 2015 - 10:19:31
Dernière modification le : mardi 7 mars 2017 - 15:22:57
Document(s) archivé(s) le : jeudi 18 février 2016 - 11:32:59

Fichier

dmAS0172.pdf
Fichiers éditeurs autorisés sur une archive ouverte

Identifiants

  • HAL Id : hal-01229663, version 1

Collections

Citation

Federico Ardila, Tia Baker, Rika Yatchak. The combinatorics of CAT(0) cubical complexes. Alain Goupil and Gilles Schaeffer. 25th International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2013), 2013, Paris, France. Discrete Mathematics and Theoretical Computer Science, DMTCS Proceedings vol. AS, 25th International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2013), pp.849-860, 2013, DMTCS Proceedings. 〈hal-01229663〉

Partager

Métriques

Consultations de la notice

28

Téléchargements de fichiers

124