Geometric Path Problems with Violations
In this paper, we study variants of the classical geometric shortest path problem inside a simple polygon, where we allow a part of the path to go outside the polygon. Let P be a simple polygon consisting of n vertices and let s, t be a pair of points in P. Let (Formula presented.) represent the interior of P and let (Formula presented.) represent the exterior of P, i.e. (Formula presented.) and (Formula presented.). For an integer (Formula presented.), we define a k-violation path from s to t to be a path connecting s and t such that its intersection with (Formula presented.) consists of at most k segments. There is no restriction in terms of the number of segments of the path within P. The objective is to compute a path of minimum Euclidean length among all possible (Formula presented.)-violation paths from s to t. In this paper, we study this problem for (Formula presented.) and propose an algorithm that computes the shortest one-violation path in (Formula presented.) time. We show that for rectilinear polygons, the minimum length rectilinear one-violation path can be computed in (Formula presented.) time. We extend the concept of one-violation path to a one-stretch violation path. In this case, the path between s and t is composed of (a) a path in P from s to a vertex u of P, (b) a path in (Formula presented.) between u and a vertex v of P, and (c) a path in P between v and t. We show that a minimum length one-stretch violation path can be computed in (Formula presented.) time. Next, we introduce one- and two-violation monotone rectilinear path problems among a set of n disjoint axis-parallel rectangular objects. Let s, t be two points in (Formula presented.) that are not in the interior of any of the objects. In the case of one-violation monotone path problem, the desired rectilinear path from s to t consists of horizontal edges that are directed towards the right and vertical edges that are directed upwards, except for at most one edge. Similarly, in the case of a two-violation monotone path problem, all horizontal edges are directed towards the right except at most one and all vertical edges are directed upwards except at most one. Our algorithms for both of these problems run in (Formula presented.) time.
|Keywords||Geometry, Graph, Rectilinear polygons, Shortest path, Simple polygons, Violations|
Maheshwari, A, Nandy, S.C. (Subhas C.), Pattanayak, D. (Drimit), Roy, S. (Sasanka), & Smid, M. (2016). Geometric Path Problems with Violations. Algorithmica, 1–24. doi:10.1007/s00453-016-0263-3