Shortest path problem in rectangular complexes of global nonpositive curvature (Q714903)

We recall that a geodesic space \(X\) satisfies the CAT(0) property if for any \(x\), \(y\) and \(z\) arbitrary points in \(X\), and \([x,y]\), \([y,z]\) and \([z,x]\) three geodesic arcs joining them, and considering \(\Delta\) to be a triangle in the Euclidean plane with vertices \(x'\), \(y'\) and \(z'\), and sides \([x',y']\), \([y',z']\) and \([z',x']\) whose lengths are equal respectively to those of \([x,y]\), \([y,z]\) and \([z,x]\), then the natural map from the union \([x,y]\cup[y,z]\cup[z,x]\) (with distances between points measured in \(X\)) to the edges of \(\Delta\) is distance non-decreasing. The terminology \textit{CAT} is due to Gromov, who introduced it in honor of Cartan, Aleksandrov and Toponogov. The present paper deals precisely with CAT(0) metric spaces and introduces an algorithm for answering two-point distance queries in CAT(0) rectangular complexes and two of their subclasses, ramified rectilinear polygons and squaregraphs. A formal description of the algorithm is presented, and its complexity is analyzed. In particular, the authors show that the shortest path \(\gamma (x,y)\) between two points \(x,y\) of a CAT(0) box complex \(K\) is contained in the subcomplex induced by the graph interval \(I(p,q)\) between two vertices \(p,q\) belonging to the cells containing \(x\) and \(y\), respectively. In addition, they also show that this subcomplex \({K}(I(p,q))\) can be unfolded in the \(k\)-dimensional space \(\mathbb R^{k}\) (where \(k\) is the dimension of a largest cell of \({K}(I(p,q))\)) in a such a way that the shortest path between any two points is the same in \({K}(I(p,q))\) and in the unfolding of \({K}(I(p,q)).\)