On Bounded Leg Shortest Paths Problems |
| |
Authors: | Liam Roditty Michael Segal |
| |
Affiliation: | 1.School of Computer Science,Tel Aviv University,Tel Aviv,Israel;2.Communication Systems Engineering Department,Ben-Gurion University of the Negev,Beer-Sheva,Israel |
| |
Abstract: | 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: |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|