×

\(k\)-link shortest paths in weighted subdivisions. (English) Zbl 1161.68814

Dehne, Frank (ed.) et al., Algorithms and data structures. 9th international workshop, WADS 2005, Waterloo, Canada, August 15–17, 2005. Proceedings. Berlin: Springer (ISBN 3-540-28101-0/pbk). Lecture Notes in Computer Science 3608, 325-337 (2005).
Summary: We 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 results to obtain approximation algorithms that yield a path having \(O(k)\) links and weighted length at most \((1+\epsilon)\) times the weighted length of an optimal \(k\)-link path, for any fixed \(\epsilon > 0\). Some of our results make use of a new solution for the 1-link case, based on computing optimal solutions for a special sum-of-fractionals (SOF) problem. We have implemented a system, based on the CORE library, for computing optimal 1-link paths; we experimentally compare our new solution with a previous method for 1-link optimal paths based on a prune-and-search scheme.
For the entire collection see [Zbl 1087.68001].

MSC:

68U05 Computer graphics; computational geometry (digital and algorithmic aspects)
68Q25 Analysis of algorithms and problem complexity
68W25 Approximation algorithms
PDFBibTeX XMLCite
Full Text: DOI