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
    0 references
    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

    Identifiers

    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references