caa a22 4500 445804912 CHVBK 20180317145153.0 cr unu---uuuuu 170323e20110401xx s 000 0 eng 10.1007/s00453-009-9322-3 doi (NATIONALLICENCE)springer-10.1007/s00453-009-9322-3 On Bounded Leg Shortest Paths Problems [Elektronische Daten] [Liam Roditty, Michael Segal] 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: 1.An algorithm for the apBLSP problem in any l p-metric which, for any fixed ε>0, computes in O(n 3(log 3 n+log 2 n⋅ε −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.2.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.3.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 etal.(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. Springer Science+Business Media, LLC, 2009 Bounded leg shortest problem nationallicence Geometric spanners nationallicence Distance query nationallicence Roditty Liam School of Computer Science, Tel Aviv University, 69978, Tel Aviv, Israel aut Segal Michael Communication Systems Engineering Department, Ben-Gurion University of the Negev, 84105, Beer-Sheva, Israel aut Algorithmica Springer-Verlag 59/4(2011-04-01), 583-600 0178-4617 59:4<583 2011 59 453 https://doi.org/10.1007/s00453-009-9322-3 text/html Onlinezugriff via DOI 1 research-article jats NATIONALLICENCE 856 40 https://doi.org/10.1007/s00453-009-9322-3 text/html Onlinezugriff via DOI NATIONALLICENCE 700 1- Roditty Liam School of Computer Science, Tel Aviv University, 69978, Tel Aviv, Israel aut NATIONALLICENCE 700 1- Segal Michael Communication Systems Engineering Department, Ben-Gurion University of the Negev, 84105, Beer-Sheva, Israel aut NATIONALLICENCE 773 0- Algorithmica Springer-Verlag 59/4(2011-04-01), 583-600 0178-4617 59:4<583 2011 59 453 Metadata rights reserved Springer special CC-BY-NC licence nationallicence BK010053 XK010053 XK010000 NATIONALLICENCE NATIONALLICENCE NL-springer