Shortest path problem in rectangular complexes of global nonpositive curvature (Q714903)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Shortest path problem in rectangular complexes of global nonpositive curvature |
scientific article |
Statements
Shortest path problem in rectangular complexes of global nonpositive curvature (English)
0 references
12 October 2012
0 references
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)).\)
0 references
CAT(0) space
0 references
shortest path
0 references
non-positive curvature
0 references
comparison inequality
0 references
geodesic
0 references
metric space
0 references
geometric group theory
0 references