Shortest path problem in rectangular complexes of global nonpositive curvature

DOI10.1016/J.COMGEO.2012.04.002MaRDI QIDQ714903zbMATHOpenAlexFDO

Authors Victor Chepoi, Daniela Maftuleac

Publication date 12 October 2012

Published in Computational Geometry (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1010.0852

zbMATH Keywords

CAT(0) spacegeodesicmetric spaceshortest pathgeometric group theorycomparison inequalitynon-positive curvature

Mathematics Subject Classification ID

Numerical optimization and variational techniques (65K10) Existence theories for optimal control problems involving partial differential equations (49J20) Global geometric and topological methods (à la Gromov); differential geometric analysis on metric spaces (53C23) Direct methods ((G)-spaces of Busemann, etc.) (53C70) Topological methods in group theory (57M07) Geometric measure and integration theory, integral and normal currents in optimization (49Q15) Global surface theory (convex surfaces à la A. D. Aleksandrov) (53C45)

Abstract: CAT(0) metric spaces constitute a far-reaching common generalization of Euclidean and hyperbolic spaces and simple polygons: any two points x and y of a CAT(0) metric space are connected by a unique shortest path {gamma}(x,y). In this paper, we present an efficient algorithm for answering two-point distance queries in CAT(0) rectangular complexes and two of theirs subclasses, ramified rectilinear polygons (CAT(0) rectangular complexes in which the links of all vertices are bipartite graphs) and squaregraphs (CAT(0) rectangular complexes arising from plane quadrangulations in which all inner vertices have degrees geq4). Namely, we show that for a CAT(0) rectangular complex K with n vertices, one can construct a data structure D of size $O(n^2)$ so that, given any two points x,y in K, the shortest path {gamma}(x,y) between x and y can be computed in O(d(p,q)) time, where p and q are vertices of two faces of K containing the points x and y, respectively, such that {gamma}(x,y) is contained in K(I(p,q)) and d(p,q) is the distance between p and q in the underlying graph of K. If K is a ramified rectilinear polygon, then one can construct a data structure D of optimal size O(n) and answer two-point shortest path queries in O(d(p,q)log{Delta}) time, where {Delta} is the maximal degree of a vertex of G(K). Finally, if K is a squaregraph, then one can construct a data structure D of size O(nlogn) and answer two-point shortest path queries in O(d(p,q)) time.

Recommendations

• ALGORITHMS FOR DISTANCE PROBLEMS IN PLANAR COMPLEXES OF GLOBAL NONPOSITIVE CURVATURE
• Shortest paths and convex hulls in 2D complexes with non-positive curvature
• A polynomial time algorithm to compute geodesics in CAT(0) cubical complexes
• Geodesics in CAT(0) cubical complexes
• A polynomial time algorithm to compute geodesics in CAT(0) cubical complexes

Cited in

(12)

• Minimum path problems in normed spaces: Reflection and refraction
• Weakly Modular Graphs and Nonpositive Curvature
• Shortest paths and convex hulls in 2D complexes with non-positive curvature
• A polynomial time algorithm to compute geodesics in CAT(0) cubical complexes
• Old and new challenges in Hadamard spaces
• Sample Compression Schemes for Balls in Graphs
• ALGORITHMS FOR DISTANCE PROBLEMS IN PLANAR COMPLEXES OF GLOBAL NONPOSITIVE CURVATURE
• Length minimizing paths in the hyperbolic plane: proof via paired subcalibrations
• Geodesics in CAT(0) cubical complexes
• A polynomial time algorithm to compute geodesics in CAT(0) cubical complexes
• CAT(0) is an algorithmic property
• Distance and routing labeling schemes for cube-free median graphs

This page was built for publication: Shortest path problem in rectangular complexes of global nonpositive curvature

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q714903)