Let V be a set of points in a d‐dimensional l
p
‐metric space. Let s,t∈V and let L be a real number. An L‐bounded leg path from s to t is an ordered set of points which connects s to t such that the leg between any two consecutive points in the set has length of at most L. The minimal path among all these paths is the L‐bounded leg shortest path from s to t. In the s–t Bounded Leg Shortest Path (stBLSP) problem we are given two points s and t and a real number L, and are required to compute an L‐bounded leg shortest path from s to t. In the All‐Pairs Bounded Leg Shortest Path (apBLSP) problem we are required to build a data structure that, given any two query points from V and a real number L, outputs the length of the L‐bounded leg shortest path (a distance query) or the path itself (a path query). In this paper we obtain the following results:
An algorithm for the apBLSP problem in any lp‐metric which, for any fixed ϵ>0, computes in O(n3(log3n+log2n·ϵ-d)) time a data structure which approximates any bounded leg shortest path within a multiplicative error of (1+ϵ). It requires O(n
2log n) space and distance queries are answered in O(log log n) time.
An algorithm for the stBLSP problem that, given s,t∈V and a real number L, computes in O(n · polylog(n)) the exact L‐bounded shortest path from s to t. This algorithm works in l
1 and l
∞ metrics. In the Euclidean metric we also obtain an exact algorithm but with a running time of O(n
4/3+ϵ
), for any ϵ>0.
For any weighted directed graph we give a data structure of size O(n
2.5log n) which is capable of answering path queries with a multiplicative error of (1+ϵ) in O(log log n+ℓ) time, where ℓ is the length of the reported path.
Our results improve upon the results given by Bose et al. (Comput. Geom. Theory Appl. 29:233–249, 2004). Our algorithms incorporate several new ideas along with an interesting observation made on geometric spanners, which is of independent interest.
