# A polynomial time algorithm to compute geodesics in CAT(0) cubical complexes

arXiv: https://arxiv.org/abs/1710.09932 · HTML: https://mlsanity.com/paper/1710.09932/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 26 Oct 2017.

## Built on by (most cited first, 1 of 1)

- [Horoballs and the subgradient method](https://mlsanity.com/paper/2403.15749/) (2024)

## Abstract (arXiv)

This paper presents the first polynomial time algorithm to compute geodesics in a CAT(0) cubical complex in general dimension. The algorithm is a simple iterative method to update breakpoints of a path joining two points using Miller, Owen and Provan's algorithm (2015) as a subroutine. Our algorithm is applicable to any CAT(0) space in which geodesics between two close points can be computed, not limited to CAT(0) cubical complexes.