Shortest path problem in rectangular complexes of global nonpositive curvature

DOI10.1016/J.COMGEO.2012.04.002zbMATH Open1259.65099arXiv1010.0852OpenAlexW3105515057MaRDI QIDQ714903FDOQ714903

Authors: Victor Chepoi, Daniela Maftuleac 

Publication date: 12 October 2012

Published in: Computational Geometry (Search for Journal in Brave)

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.

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

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

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)

Cited In (12)

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

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)