کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
414704 | 681009 | 2013 | 14 صفحه PDF | دانلود رایگان |
![عکس صفحه اول مقاله: Shortest path problem in rectangular complexes of global nonpositive curvature Shortest path problem in rectangular complexes of global nonpositive curvature](/preview/png/414704.png)
CAT(0)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)CAT(0) metric space are connected by a unique shortest path γ(x,y)γ(x,y). In this paper, we present an efficient algorithm for answering two-point distance queries in CAT(0)CAT(0) rectangular complexes and two of theirs subclasses, ramified rectilinear polygons (CAT(0)CAT(0) rectangular complexes in which the links of all vertices are bipartite graphs) and squaregraphs (CAT(0)CAT(0) rectangular complexes arising from plane quadrangulations in which all inner vertices have degrees ⩾4). Namely, we show that for a CAT(0)CAT(0) rectangular complex KK with n vertices, one can construct a data structure DD of size O(n2)O(n2) so that, given any two points x,y∈Kx,y∈K, the shortest path γ(x,y)γ(x,y) between x and y can be computed in O(d(p,q))O(d(p,q)) time, where p and q are vertices of two faces of KK containing the points x and y , respectively, such that γ(x,y)⊂K(I(p,q))γ(x,y)⊂K(I(p,q)) and d(p,q)d(p,q) is the distance between p and q in the underlying graph of KK. If KK is a ramified rectilinear polygon, then one can construct a data structure DD of optimal size O(n)O(n) and answer two-point shortest path queries in O(d(p,q)logΔ) time, where Δ is the maximal degree of a vertex of G(K)G(K). Finally, if KK is a squaregraph, then one can construct a data structure DD of size O(nlogn) and answer two-point shortest path queries in O(d(p,q))O(d(p,q)) time.
Journal: Computational Geometry - Volume 46, Issue 1, January 2013, Pages 51–64