Computing a Shortest k-Link Path in a Polygon

The authors consider the problem of finding a shortest polygonal path from s to t within a simple polygon P, subject to the restriction that the path have at most k links (edges). They give an algorithm to compute a k-link path with length at most (1 + epsilon ) times the length of a shortest k-link path, for any error tolerance epsilon >0. The algorithm runs in time O(n/sup 3/k/sup 3/ log (Hk/ epsilon /sup 1/k/)), where N is the largest integer coordinate among the n vertices of P. They also study the more general problem of approximating shortest k-link paths in polygons with holes. In this case, they give an algorithm that returns a path with at most 2k links and length at most that of a shortest k-link path; the running time is O(kE/sup 2/), where E is the number of edges in the visibility graph. Finally, they study the bicriteria path problem in which the two criteria are link length and 'total turn' (the integral of mod Delta theta mod along a path). They obtain in an exact polynomial-time algorithm for polygons with holes. >

Authors

• Joseph S. B. Mitchell
• Christine D. Piatko
• Esther M. Arkin

Keywords

• Polynomials
• Contracts
• Computational geometry
• Laboratories
• Computer science
• Link Path
• Running Time
• Path Length
• Clockwise
• Shortest Path
• Local Optimum
• Dynamic Programming
• Problem Of Finding
• Pair Of Points
• Optimal Path
• Visibility Graph
• Applied Maths
• Exact Algorithm
• Binary Search
• Stony Brook
• Link Distance
• Tangent Point
• Geodesic Path
• Outline Of The Proof
• Pair Of Edges