Cited By
View all- Berger AGrigoriev APeeters RUsotskaya N(2015)On Time-Optimal Trajectories in Non-Uniform MediumsJournal of Optimization Theory and Applications10.1007/s10957-014-0590-y165:2(586-626)Online publication date: 1-May-2015
Approximating minimum-cost polygonal paths of bounded number of links in weighted subdivisions
Authors: 
Ovidiu Daescu, Joseph S. B. Mitchell, Simeon Ntafos, 
James D. Palmer, Chee K. YapAuthors Info & Claims
Pages 483 - 484
Abstract
This video illustrates the k-LinkSolver software for computing k-link shortest paths in weighted regions. The k-LinkSolver implements methods to find paths of length at most (1+ε) times the length of a shortest k-link path, for any fixed ε>0, and having at most 2k−1 links. The methods implemented are an improvement over the previously known (1+ε)-approximation algorithms, which guarantee at most 5k−2 links.
References
[1]
L. Aleksandrov, A. Maheshwari, and J.-R. Sack. Determining approximate shortest paths on weighted polyhedral surfaces. Journal of the ACM, 52(1):25--53, 2005.
[2]
D. Z. Chen, O. Daescu, X. Hu, X. Wu, and J. Xu. Determining an optimal penetration among weighted regions in two and three dimensions. Journal of Combinatorial Optimization, 5(1):59--79, 2001.
[3]
O. Daescu. Improved Optimal Weighted Links Algorithms. In Proc. 2nd International Workshop on Computational Geometry and Applications, Vol 2331 of Lecture Notes Comput. Sci., pages 6--74. Springer-Verlag, 2002.
[4]
O. Daescu, J. S. B. Mitchell, S. Ntafos, J. D. Palmer, and C. K. Yap. k-link shortest paths in weighted subdivisions. In Proc. 9th Workshop Algorithms Data Struct., Vol 3608 of Lecture Notes Comput. Sci., pages 325--337. Springer-Verlag, 2005.
[5]
J. S. B. Mitchell and C. H. Papadimitriou. The weighted region problem: finding shortest paths through a weighted planar subdivision. J. ACM, 38:18--73, 1991.
Index Terms
- Approximating minimum-cost polygonal paths of bounded number of links in weighted subdivisions
Recommendations
On Approximating Shortest Paths in Weighted Triangular Tessellations
WALCOM: Algorithms and ComputationAbstractWe study the quality of weighted shortest paths when a continuous 2-dimensional space is discretized by a weighted triangular tessellation. In order to evaluate how well the tessellation approximates the 2-dimensional space, we study three types ...
k-link shortest paths in weighted subdivisions
WADS'05: Proceedings of the 9th international conference on Algorithms and Data StructuresWe study the shortest path problem in weighted polygonal subdivisions of the plane, with the additional constraint of an upper bound, k, on the number of links (segments) in the path. We prove structural properties of optimal paths and utilize these ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
Copyright © 2006 ACM.
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]
Sponsors
Publisher
Association for Computing Machinery
New York, NY, United States
Publication History
Published: 05 June 2006
Check for updates
Qualifiers
- Article
Conference
Acceptance Rates
Overall Acceptance Rate 625 of 1,685 submissions, 37%
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- View Citations1Total Citations
- 201Total Downloads
- Downloads (Last 12 months)0
- Downloads (Last 6 weeks)0
Reflects downloads up to 11 Dec 2024
Other Metrics
Citations
Cited By
View all- Berger AGrigoriev APeeters RUsotskaya N(2015)On Time-Optimal Trajectories in Non-Uniform MediumsJournal of Optimization Theory and Applications10.1007/s10957-014-0590-y165:2(586-626)Online publication date: 1-May-2015
View Options
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in