skip to main content
10.5555/1283383.1283466acmconferencesArticle/Chapter ViewAbstractPublication PagessodaConference Proceedingsconference-collections
Article

On bounded leg shortest paths problems

Published: 07 January 2007 Publication History

Abstract

Let V be a set of points in a d-dimensional lp-metric space. Let s, t ε V and let L be any 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 is 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 any 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 present first an algorithm for the apBLSP problem in any lp-metric which, for any fixed ε > 0, computes in O(n3 n = log2 n · ε-d)) time a data structure which approximates any bounded leg shortest path within a multiplicative error of (1 + ε). It requires O(n2log n) space and distance queries are answered in O (log log n) time. This improves on an algorithm with running time of O(n5) given by Bose et al. in [8]. We present also an algorithm for the stBLSP problem that, given s, tV 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 l1 and l metrics. In the Euclidean metric we also obtain an exact algorithm but with a running time of O(n4/3+ε), for any ε > 0. We end by showing that for any weighted directed graph there is a data structure of size O(n2.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. [8]. Our algorithms incorporate several new ideas along with an interesting observation made on geometric spanners, which is of an independent interest.

References

[1]
Pankaj K. Agarwal, Alon Efrat, and Micha Sharir. Vertical decomposition of shallow levels in 3-dimensional arrangements and its applications. SIAM Journal on Computing, 29:912--953, 1999.
[2]
Pankaj K. Agarwal and Jeff Erickson. Geometric range searching and its relatives. In B. Chazelle, J. E. Goodman, and R. Pollack, editors, Advances in Discrete and Computational Geometry, volume 223 of Contemporary Mathematics, pages 1--56. American Mathematical Society, Providence, RI, 1999.
[3]
A. Aggarwal, M. Hansen, and T. Leighton. Solving query-retrieval problems by compacting Voronoi diagrams. In Proc. 22nd Annu. ACM Sympos. Theory Comput., pages 331--340, 1990.
[4]
S. Arya, G. Das, D. M. Mount, J. S. Salowe, and M. Smid. Euclidean spanners: short, thin, and lanky. In Proceedings of the 27th ACM Symposium on the Theory of Computing, pages 489--498, 1995.
[5]
S. Arya, D. M. Mount, and M. Smid. Dynamic algorithms for geometric spanners of small diameter: Randomized solutions. Computational Geometry: Theory and Applications, 13:91--107, 1999.
[6]
S. Baswana and S. Sen. A simple linear time algorithm for computing a (2k-1)-spanner of O(n1+1/k) size in weighted graphs. In ICALP: Annual International Colloquium on Automata. Languages and Programming, 2003.
[7]
J. L. Bentley and J. B. Saxe. Decomposable searching problems I: Static-to-dynamic transformations. J. Algorithms, 1:301--358, 1980.
[8]
P. Bose, A. Meheswari, G. Narasimhan, M. Smid, and N. Zeh. Approximating geometric bottleneck shortest paths. Computational Geometry: Theory and Applications, 29:233--249, 2004.
[9]
P. B. Callahan and S. R. Kosaraju. A decomposition of multidimensional point sets with applications to κ-nearest-neighbors and n-body potential fields. Journal of the ACM, 42:67--90, 1995.
[10]
T. M. Chan. Dynamic planar convex hull operations in near-logarithmic amortized time. J. ACM, 48:1--12, 2001.
[11]
Timothy M. Chan. A dynamic data structure for 3-d convex hulls and 2-d nearest neighbor queries. ACM-SIAM Symposium on Discrete Algorithms, 2006.
[12]
Timothy M. Chan and Alon Efrat. Fly cheaply: On the minimum fuel consumption problem. J. Algorithms, 41:330--337, 2001.
[13]
Bernard Chazelle. On the convex layers of a planar set. IEEE Trans. Inform. Theory, IT-31(4):509--517, July 1985.
[14]
Bernard Chazelle and F. P. Preparata. Halfspace range search: An algorithmic application of κ-sets. Discrete Comput. Geom., 1:83--93, 1986.
[15]
Mark de Berg, Marc van Kreveld, Mark Overmars, and Otfried Schwarzkopf. Computational Geometry: Algorithms and Applications. Springer-Verlag, Berlin, Germany, 2nd edition, 2000.
[16]
Michael Elkin and David Peleg. (1+epsilon, beta)-spanner constructions for general graphs. In STOC, pages 173--182, 2001.
[17]
D. Eppstein. Dynamic Euclidean minimum spanning trees and extrema of binary functions. Discrete Comput. Geom., 13:111--122, 1995.
[18]
J. Hershberger and S. Suri. Applications of a semi-dynamic convex hull algorithm. BIT, 32:249--267, 1992.
[19]
S. Kapoor and M. Smid. New techniques for exact and approximate dynamic closest-point problems. SIAM J. Comput., 25:775--796, 1996.
[20]
J. Matousek. Efficient partition trees. Discrete Comput. Geom., 8:315--334, 1992.
[21]
S. Pettie. A new approach to all-pairs shortest paths on real-weighted graphs. Theoretical Computer Science, 312(1):47--74, 2004.
[22]
M. Thorup. Undirected single-source shortest paths with positive integer weights in linear time. Journal of the ACM, 46(3):362--394, 1999.
[23]
Mikkel Thorup and Uri Zwick. Approximate distance oracles. In STOC, pages 183--192, 2001.
[24]
P. M. Vaidya. A sparse graph almost as good as the complete graph on points in K dimensions. Discrete & Computational Geometry, 6:369--381, 1991.
[25]
U. Zwick. All pairs shortest paths using bridging sets and rectangular matrix multiplication. Journal of the ACM, 49(3):289--317, 2002.

Cited By

View all
  • (2008)Bounded-leg distance and reachability oraclesProceedings of the nineteenth annual ACM-SIAM symposium on Discrete algorithms10.5555/1347082.1347130(436-445)Online publication date: 20-Jan-2008

Recommendations

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences
SODA '07: Proceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms
January 2007
1322 pages
ISBN:9780898716245
  • Conference Chair:
  • Harold Gabow

Sponsors

Publisher

Society for Industrial and Applied Mathematics

United States

Publication History

Published: 07 January 2007

Check for updates

Qualifiers

  • Article

Acceptance Rates

SODA '07 Paper Acceptance Rate 139 of 382 submissions, 36%;
Overall Acceptance Rate 411 of 1,322 submissions, 31%

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)4
  • Downloads (Last 6 weeks)0
Reflects downloads up to 22 Feb 2025

Other Metrics

Citations

Cited By

View all
  • (2008)Bounded-leg distance and reachability oraclesProceedings of the nineteenth annual ACM-SIAM symposium on Discrete algorithms10.5555/1347082.1347130(436-445)Online publication date: 20-Jan-2008

View Options

Login options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Figures

Tables

Media

Share

Share

Share this Publication link

Share on social media