Approximate Shortest Paths in Polygons with Violations.

We study the shortest k -violation path problem in a simple polygon. Let P be a simple polygon in ℝ 2 with n vertices and let s , t be a pair of points in P. Let i n t (P) represent the interior of P. Let P ̃ = ℝ 2 \ i n t (P) represent the exterior of P. For an integer k ≥ 0 , the shortest k -violation path problem in P is the problem of computing the shortest path from s to t in P , such that at most k path segments are allowed to be in P ̃. The subpaths of a k -violation path are not allowed to bend in P ̃. For any k , we present a (1 + 2 𝜖) factor approximation algorithm for the problem that runs in O (n 2 σ 2 k log n 2 σ 2 + n 2 σ 2 k) time. Here σ = O (log δ (L r)) and δ , L , r are geometric parameters. [ABSTRACT FROM AUTHOR]