2026-07-20T01:58:59Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:9082 2024-03-06T10:43:19Z ddc:004 open_access

A Polynomial Time Algorithm to Compute Geodesics in CAT(0) Cubical Complexes Hayashi, Koyo Geodesic CAT(0) Space Cubical Complex 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 (Adv. in Appl. Math, 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Koyo Hayashi 2018 Is Part Of LIPIcs, Volume 107, 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2018.78 urn:nbn:de:0030-drops-90822 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2018.78 eng https://creativecommons.org/licenses/by/3.0/legalcode