Keywords

1 Introduction

Let P be a simple polygon in \(\mathbb {R}^2\) with n vertices. Let int(P) and \(\varDelta (P)\) represent the interior and the boundary of the polygon P respectively and \(\tilde{P}=\mathbb {R} \setminus int(P)\) represent the exterior of P.

Shortest path in a polygon P, and its variants, is a very widely studied topic in the field of computational geometry. The shortest path problem in P is the problem of finding the shortest path that connects a pair of points \(s,t \in P\). The shortest path consists of a sequence of line segments, called path segments, that do not cross the boundary of P. For the sake of clarity, we refer to the edges of a path as path segments and the edges of P as edges. The shortest path changes directions only at the vertices of P. The sum total of the lengths of the constituent path segments is the length of the shortest path from s to t. We refer the reader to [5, 13, 17] for a detailed survey on the topic. The shortest path from a point s to all the vertices of P can be obtained in O(n) time using shortest path maps [7].

For an integer \(k \ge 0\), the k-violation shortest path in P is the problem of computing the shortest path between a pair of points \(s,t \in P\), such that the path’s intersection with \(\tilde{P}\) is at most k path segments. It must be noted, that this means we do not allow the path segments to bend in \(\tilde{P}\). Maheshwari et al. [14] proposed an algorithm that computes the shortest one violation path for a pair of points \(s,t \in P\) in \(O(n^3)\) time. The problem that we study in this paper is inspired by the shortest one violation path. In the same paper, two other shortest path problems where some constraints are violated in some restricted way are studied. They study the one-stretch violation path problem and monotone rectilinear path problems with violations. They propose an \(O(n \log n \log \log n)\) time algorithm for shortest one-stretch violation path and an \(O(n \log n)\) time algorithm for shortest one violation monotone rectilinear path problem.

To compute the shortest k-violation we use the discretization technique of Aleksandrov et al. [2]. They used the mentioned technique to solve the problem of computing the shortest path in weighted terrains. The technique consists of discretizing the faces of the terrain by inserting Steiner points on the edges of the terrain. Then a weighted graph G is constructed where nodes of G are the Steiner points and the vertices of the terrain. Then the shortest path is computed on G using Dijkstra’s shortest path algorithm.

1.1 Related Works

Lanthier et al. [12] used Steiner points to discretize the edges of a triangulated polyhedral surface, where faces of the triangulation have weights associated with them, to compute a \((1+\epsilon )\)-factor weighted shortest path on the polyhedral surface. Their algorithm runs in \(O(n^3 \log n)\) time. This approach of placing Steiner points on the edges of a triangulated weighted polyhedral surface was used by Aleksandrov et. al [2] to compute a \((1+\epsilon )\), for a given \(\epsilon > 0\), approximate shortest path between a pair of points. Their algorithm runs in \(O(mn \log mn + nm^2)\), where m and n are the number of Steiner points added and the number of vertices of the polygon respectively. Roy et al. [20] used this technique of discretization using Steiner points to compute a \(O(1+\epsilon )\) shortest descending path between a pair of points on the surface of a polyhedral terrain. The running time of this algorithm is \(O(mn \log mn + nm^2)\). Cheng et al. [4] used a strategy of placing Steiner points on the edges of the triangulation of the polyhedral surface different from the previously mentioned works to compute a \((1+\epsilon )\)-factor shortest path on the planar subdivision. In this problem, the weight of a path segment of a path on a face of the triangulation is the distance between the two points where the path intersects with the face. This distance is determined by a convex distance function, possibly asymmetric, associated with the face. Different faces can have different associated convex functions. The running time of the algorithm does not depend on the geometric parameters like the minimum angle in the subdivision. They achieve this by restricting the placement of the Steiner points only on the edges of the triangulation that are contained in an ellipse whose diameter is \(\frac{4}{3}\rho ||s ~ t||\), where \(\rho \ge 1\) and ||s t|| is the global geodesic shortest path between s and t. The time complexity of the algorithm is \(O(\frac{\rho ^2 \log \rho }{\epsilon ^2}n^3 \log \frac{\rho n}{\epsilon })\). Their strategy of discretization cannot be used in computing approximate k-violation path directly because, while the global geodesic shortest path is a lower bound for the shortest path in their problem, it is an upper bound for the shortest k-violation path, because unless the line segment \(\overline{st}\) lies completely within a polygon P, there always exists a path with at least one violation whose length is shorter than \(\overline{st}\) [14].

Maheshwari et al. [14] studied the problem of computing the shortest path between points s and t in a polygon P such that the path’s intersection with \(\tilde{P}\) is at most one path segment. This is the most related problem to the problem of shortest k violation path in a polygon. They propose an algorithm that computes the shortest one violation path \(\pi _1(s,t)\) in \(O(n^3)\) time. They use a structure called shortest path map, due to [9], which is used to compute the shortest path from a source s to all points in a polygon P. A shortest path map splits the boundary of a polygon into open intervals called component pieces. Each component piece has an associated vertex of the polygon, which is called a parent vertex. For all points in the component piece, the shortest path from s in P passes through the parent vertex. Then they consider the convex hull of P, CH(P). Each edge of the convex hull of P that is disjoint from the edges of P induces a region called a pocket. It must be noted here that any one violation path can pass through only one pocket out of the pockets induced by CH(P). Let us call this pocket \(P_i\). \(\pi _1(s,t)\) enters \(P_i\) through a point b on component piece I and leaves \(P_i\) through a point c component piece J. So once they fix the points b and c on I and J respectively, they compute the shortest one violation path by minimizing the function obtained by adding the lengths of (i) path from s to u, where u is the parent of I, (ii) path from v to t, where v is the parent of J, (iii) line segment \(\overline{bc}\), (iv) line segment \(\overline{ub}\) and (v) line segment \(\overline{cv}\). They do this over all the pockets.

A related topic is computing the shortest path in the plane that contains a set of polygonal obstacles. It is a very widely studied topic in the field of computational geometry [3, 6, 11, 15, 16, 18, 19, 22]. Hershberger et al. produced an optimal algorithm for the aforementioned problem that runs in \(O(n \log n)\) time [10] using the continuous Dijkstra technique. In a recent paper, Agarwal et al. [1] considered the problem of computing shortest Euclidean path in a plane with removable objects. Each object has an associated cost that must be spent to remove it from the plane. The objective is to minimize the length of the path under the constraint of a cost budget \(C >0\). They proved that the problem is NP-hard and produced a \((1+\epsilon )\)-factor FPTAS for a special case where the objects are convex polygons, that runs in \(O(\frac{nh}{\epsilon ^2} \log n \log \frac{n}{\epsilon })\), where h is the number of obstacles, n is the number of vertices of the obstacles and \(\epsilon \in (0,1)\) is a parameter defined by user. The removal cost is at most \(C \cdot (1+\epsilon )\).

Recently, Hershberger et al. [8] worked on a related problem of computing shortest path between a pair of points on a plane with a set of convex obstacles, where k obstacles from the set of obstacles can be violated. This problem can also be viewed as the problem of computing the shortest path in a plane with a set of n obstacle from which \(k \le n\) can be removed. They developed a structure called shortest k-path map, \(SPM_k\), to compute the shortest k-path that violates at most k many of the convex obstacles. Their problem is different than the shortest k-violation path in a polygon, as obstacles present in the plane are convex in case of shortest k-path. In the case of the shortest k-violation path the pockets of the given polygon can be convex as well as non-convex. The other difference is the shortest k-path can only bend at the vertices of the obstacles. Unlike shortest k-path, shortest k-violation path can bend at the edges of the given polygon P. The most important difference of all is stated by the following lemma and the succeeding observation.

Lemma 1

[8] Let \(\pi _k(t)\) and \(\tilde{\pi }_k(t')\) be two subpaths of shortest k-paths whose prefix counts are the same. Then \(\pi _k(t)\) and \(\tilde{\pi }_k(t')\) do not cross each other. Prefix count is the number of objects violated by a path.

Observation 1

A valid configuration can be constructed (Fig. 1)where two subpaths of shortest k-violation paths originating from the same source with the same prefix counts intersect each other.

Fig. 1.
figure 1

Two subpaths with the same prefix count intersecting at the point g.

Full size image

As it is stated in [8], Lemma 1 is very instrumental in constructing the data structure called shortest k-path map. Hence the same technique cannot be applied to solve the problem that we study in this paper, as shown in Observation 1.

Because of Observation 1, another nice technique called Bushwhack [23], cannot be applied to our problem. Lemma 1 in [23] states that two optimal paths cannot intersect in the interior of a region.

2 Our Contribution

We present an algorithm to compute a \((1+\epsilon )\)-factor approximate shortest k-violation path between a pair of points s and t inside a polygon P. Our algorithm runs in \(O(n^2 \sigma ^2 k\log n^2 \sigma ^2 + n^2 \sigma ^2 k)\) time, where \(\sigma = O(\log _\delta (\frac{|L|}{r}))\) and \(\delta \), L, r are geometric parameters (described in Sect. 4.1). For a special case where the pockets of P are convex and \(k=1\), we present an algorithm that computes a \((1+\epsilon )\)-factor approximate shortest one-violation path in \(O(n \sigma \log n \sigma + n \sigma ^2)\) time.

3 Preliminaries and Notations

Given a simple polygon P of n vertices and two points called the source s and destination t inside the polygon, the objective is to find a \((1+\epsilon )\)-factor shortest k-violation path that connects the two points, for any given \(\epsilon > 0\). Let int(P) denote the region inside P and \(\tilde{P} = \mathbb {R} \setminus int(P)\) be the region outside P. A k-violation path from s to t \(\pi _{k}(s,t)\) is a path in which at most k path segments lie in \(\tilde{P}\). The path segments of \(\pi _{k}(s,t)\) that lie in \(\tilde{P}\) are called the violation path segments. The path segments are not allowed to bend in \(\tilde{P}\).

Definition 1

[14] A pocket \(P_i\) is a polygonal region induced by an edge e of CH(P) that is not an edge of P. \(P_i\) is bounded by the edge e and a sequence of consecutive edges of P. The first and the last edges of the sequence are incident on the two endpoints of e.

4 Approximate Shortest One Violation Path for Polygons with Convex Pockets

For simplicity, we first deal with a constrained version of the problem when (i) \(k=1\) and (ii) the pockets of the input polygon P are convex. The solution to the constrained version helps us to characterize the general case when (i) k is a part of the input and (ii) pockets of polygon P are not necessarily convex.

4.1 Insertion of Steiner Points

We first compute the convex hull of P, CH(P). Once we have the CH(P) and the set of pockets \(P_1, P_2, \ldots , P_l\), we triangulate all the pockets \(P_i\).

Once we triangulate all the \(P_i\), we add Steiner points to the edges of the triangles of the triangulation. We insert the set of Steiner points to discretize the edges bounding the pocket \(P_i\) and the faces of triangles of the triangulation.

Steiner Points: The technique of placing Steiner points on the edges of the triangles of triangulation is the same as in [2]. For a vertex v of the triangulation, we define the minimum distance from v to the boundary of the union of faces incident on v to be \(h_v\). We define \(r_v = \epsilon h_v\), for some \(\epsilon > 0\). For each vertex v of face \(f_i\), let \(e_p\) and \(e_q\) be the two edges incident on it. We place two Steiner points \(p_1\) and \(q_1\) on \(e_p\) and \(e_q\) respectively, at distance \(r_v\) from v. By definition \(|vq_1|=|vp_1|=r_v\). Let \(\theta _v\) be the angle between \(e_q\) and \(e_p\). Now we define:

$$\begin{aligned} \delta _v = {\left\{ \begin{array}{ll} 1+\epsilon \cdot \sin \theta _v &{} \text {for } \theta _v < \frac{\pi }{2}\\ 1+\epsilon &{} \text {otherwise}\\ \end{array}\right. } \end{aligned}$$
Fig. 2.
figure 2

Steiner points.

Full size image

Now, Steiner points \(q_1,q_2,\ldots ,q_{\mu _{q}-1}\) are placed along \(e_q\), such that \(|vq_j|=r_v \delta _v^{j-1}\), where \(\mu _q=\log _{\delta _v}(\frac{|e_q|}{r_v})\). Similarly, \(p_1,p_2,\ldots ,p_{\mu _{p}-1}\) are placed along \(e_p\), where \(\mu _p=\log _{\delta _v}(\frac{|e_p|}{r_v})\) (see Fig. 2). A set of Steiner points \(q_1,q_2,\ldots ,q_{\mu _{q}-1}\) partition an edge \(e_q\) in a set of intervals \(q_1 q_2, q_2 q_3,\ldots , q_{l-1} q_l\).

Let dist(a, e) be the distance from a point a to an edge e.

Result 1

[2] \(|q_i q_{i+1}| \le \epsilon \cdot dist(q, e_p)\) and \(|p_j p_{j+1}| \le \epsilon \cdot dist(q, e_q)\) where \(0<i<\mu _q\) and \(0<j<\mu _p\), \(q \in q_i q_{i+1}\) and \(p \in p_j p_{j+1}\).

In the next step, we create a graph \(G_i\) in each pocket \(P_i\). Note that this procedure of constructing G and hence the technique discussed in the following section only work when the pockets of P are convex. We consider the Steiner points and the vertices of the triangulation in \(P_i\) as the vertices of \(G_i\). Two vertices, \(u_j\) and \(u_l\) of \(G_i\) share an arc if and only if they lie on two different edges of the face \(f_i\) or they are adjacent points on the same edge of \(f_i\). The weight on the arc \((u_j,u_l)\) is the Euclidean distance between \(u_j\) and \(u_l\). Now we construct the graph G. We create shortest path maps [7, 21]] for s and t, called \(SPM_s\) and \(SPM_t\) respectively. Typically \(SPM_s\) is used to compute the shortest paths from s to all points \(p \in P\) that stay in int(P). Using \(SPM_s\) we connect s to the Steiner points in the boundary of each pocket \(P_i\) of P. Similarly using \(SPM_t\) for t, we connect t to the Steiner points in the boundary of each pocket \(P_i\).

For the sake of clarity, we call the edges of the triangulation as edges and edges of the Steiner graph G as arcs.

Lemma 2

Total number of Steiner points added is at most \(O(n \log _\delta (\frac{|L|}{r}))\), where |L| is the length of the longest edge of the triangulation, r is the minimum among \(r_v\) and \(\delta \) is the minimum \(\delta _v\), over all v.

Proof

The number of Steiner points added in a single edge of the triangulation is \(O(\log _\delta (\frac{|L|}{r}))\). If there are \(n_i\) vertices in \(P_i\), then there are \(O(n_i)\) edges in the triangulation of \(P_i\). Hence in \(P_i\) there are \(O(n_i \log _\delta (\frac{|L|}{r}))\) Steiner points. So the total number of Steiner points added is \(\sum O(n_i \log _\delta (\frac{|L|}{r}))= O(n \log _\delta (\frac{|L|}{r}))\). \(\blacksquare \)

Lemma 3

G has \(O(n \log _\delta (\frac{|L|}{r}))\) vertices and \(O(n \log ^2_\delta (\frac{|L|}{r}))\) arcs.

Proof

The vertices of G are the Steiner points and the points s and t. By Lemma 2, the total number of Steiner points added is at most \(O(n \log _\delta (\frac{|L|}{r}))\), hence G has \(O(n \log _\delta (\frac{|L|}{r}))\) many vertices. There exists an arc between two Steiner points in G if and only if they belong to two different edges of the same face \(f_i\) of the triangulation or they are adjacent points on the same edge of \(f_i\). Hence each Steiner point is connected with arcs to \(O(\log _\delta (\frac{|L|}{r}))\) many Steiner points. There are arcs between s and the Steiner points on the edges of \(\varDelta (P)\) that bound the pockets. Similarly, there are arcs between t and the Steiner points on the edges of \(\varDelta (P)\) that bound the pockets. Since there are \(O(n \log _\delta (\frac{|L|}{r}))\) vertices in G, therefore there can be at most \(O(n \log ^2_\delta (\frac{|L|}{r}))\) arcs in G. \(\blacksquare \)

For simplicity, hereinafter \(\sigma = O(\log _\delta (\frac{|L|}{r}))\).

4.2 Approximating Shortest One Violation Path for Polygons with Convex Pockets

Let \(\pi _1 = [s_,o_1,o_2,\ldots ,o_l,t]\) be the optimal one violation path that passes through a sequence edges \(e_1,e_2,\dots ,e_l\) of the triangulation in a pocket. In each edge \(e_i\) the path \(\pi _1\) passes through a point \(o_i\) between two Steiner points \(a_{\alpha {i}}\) and \(b_{\alpha {i}}\). We assign the Steiner point closer to \(o_i\) among \(a_{\alpha {i}}\) and \(b_{\alpha {i}}\) to \(u_{\alpha _i}\). Let \(\pi ^*(s,t)=[s, u_{\alpha _1},u_{\alpha _2},\ldots ,u_{\alpha _l},t]\) be a path in G.

Lemma 4

The length of a the path \(\pi ^*(s,t)\) with path segments through the Steiner points on the edges of the triangular faces of a pocket \(P_i\) is at most \((1+\epsilon )\cdot \pi _1(s,t)\)

Proof

\(\pi ^*(s,t)=|s u_{\alpha _1}|+ |u_{\alpha _1} u_{\alpha _2}| + |u_{\alpha _2} u_{\alpha _3}| + \ldots + |u_{\alpha _{l-1}} u_{\alpha _l}| + |u_{\alpha _l} t|\)

\(\le |s o_1|+ |o_1 u_{\alpha _1}| + |u_{\alpha _1} o_1| + |o_1 o_2|+ |o_2 u_{\alpha _2}| + |u_{\alpha _2} o_2| + |o_2 o_3| + |o_3 u_{\alpha _3}| + |u_{\alpha _3} o_3| + \ldots + |u_{\alpha _{l-1}} u_{\alpha _l}| + |u_{\alpha _l} t|\)

\(=|s o_1| + |o_1 o_2| + |o_2 o_3| + \ldots + |o_{l-1} o_{l}| + ||o_l t| + 2 \{|o_1 u_{\alpha _1}| + |o_2 u_{\alpha _2}| + \ldots + |o_l u_{\alpha _l}|\}\)

\(\le |s o_1| + |o_1 o_2| + |o_2 o_3| + \ldots + |o_{l-1} o_{l}| + ||o_l t| + 2 \epsilon \{|o_1 o_2| + |o_2 o_3| + \ldots + |o_{l-1} o_{l}|\}\) (using Result 1)

\(\le (1 + 2 \epsilon ) \cdot \pi _1(s,t)\) \(\blacksquare \)

Fig. 3.
figure 3

Approximate one violation shortest path \(\pi ^*_1(s,t)\).

Full size image

From the above lemma, we know that \(\pi ^*(s,t) \le (1 + 2 \epsilon ) \cdot \pi _1(s,t)\). Dijkstra’s algorithm may produce a different path \(\pi ^{**}(s,t)\) (Fig. 3a). Dijkstra’s algorithm always produces a path of shortest length, therefore \(\pi ^{**}(s,t) \le \pi ^*(s,t)\). Now, \(\pi ^{**}(s,t)\) is not a feasible solution to the problem, since we don’t allow the one violation path to bend in \(\tilde{P}\) and while passing through the edges of the triangulation in a pocket, \(\pi ^{**}(s,t)\) might have multiple bends. Therefore, once we obtain \(\pi ^{**}(s,t)\), we can compute the approximate one violation shortest path \(\pi ^*_1(s,t)\) by replacing the intermediate path segments of \(\pi ^{**}(s,t)\) between \(u_{\alpha _1}\) and \(u_{\alpha _l}\) by a line segment \(\overline{u_{\alpha _1} ~ u_{\alpha _l}}\), where \(u_{\alpha _1}\) and \(u_{\alpha _l}\) are the first and last Steiner points between s and t (Fig. 3b). Next we argue that \(\pi ^*_1(s,t)=[s,u_{\alpha _1},u_{\alpha _l},t]\) is a \((1+\epsilon )\)-factor approximate one violation shortest path.

Lemma 5

\(\pi ^*_1(s,t) \le (1 + 2 \epsilon ) \cdot \pi _1(s,t)\)

Proof

By Lemma 4, \(\pi ^{**}(s,t) \le (1 + 2 \epsilon ) \cdot \pi _1(s,t)\). Since, to compute \(\pi ^*_1(s,t)\) we remove all the intermediate path segments between \(u_{\alpha _1}\) and \(u_{\alpha _l}\), and connect them with a line segment, therefore \(\pi ^*_1(s,t) \le \pi ^{**}(s,t)\). Thus, \(\pi ^*_1(s,t) \le (1 + 2 \epsilon ) \cdot \pi _1(s,t)\). \(\blacksquare \)

Theorem 1

For a polygon P whose pockets are convex, a \((1+\epsilon )\) approximate one violation shortest path between any pair of points s and t can be computed in \(O(n \sigma \log n \sigma + n \sigma ^2)\), where \(\sigma = O(\log _\delta (\frac{|L|}{r}))\).

Proof

The time complexity of our technique is the same as the computation of single source shortest path on G using Dijkstra’s algorithm with Fibonacci heap. \(\blacksquare \)

4.3 Limitations of the Technique

The technique proposed Sects. 4.1 and 4.2 works under the assumption that at least one end of the interval \(p_j p_{j+1}\) is visible from at least one end of the interval \(q_l q_{l+1}\), where \(p_j p_{j+1}\) is the interval through which \(\pi _1(s,t)\) enters the pocket and \(q_l q_{l+1}\) is the interval through which \(\pi _1(s,t)\) leaves the pocket and enters int(P) again. But observe that, if the pockets are not convex, it might not be possible to connect an endpoint of the interval of \(p_j p_{j+1}\) to an endpoint of the interval \(q_l q_{l+1}\) with a line segment even though the shortest path passes through a point \(o_j\) between \(p_j p_{j+1}\) and \(o_l\) between \(q_l q_{l+1}\). Hence the technique discussed in the aforementioned subsections will always produce a \(\pi ^*_1(s,t)\) if for all s, t, if it can be ensured that an endpoint of the interval \(p_j p_{j+1}\) is always visible to an endpoint of the interval \(q_l q_{l+1}\). As a consequence of this observation, this technique will always produce a \((1+\epsilon )\)-factor approximate shortest one violation path under the restriction that all pockets of the polygon P are convex.

To address this issue we construct the graph G in the way described in the next section and present an algorithm for approximating shortest k-violation path in polygons, for any k, with pockets of arbitrary shapes (convex or otherwise).

5 Approximating Shortest k-violation Path

We compute the convex hull CH(P) and then we triangulate it. We add Steiner points along the edges of a face of the triangulation \(f_i \in int(P)\), using the strategy as used in Sect. 4.1. In each face \(f_i\), each pair of Steiner points p and q on the edges of \(f_i\) are connected with an arc if and only if p and q are adjacent Steiner points on the same edge of \(f_i\) or p and q are placed on two different edges of \(f_i\). The weight of the arc (pq) is the length of the arc.

Now, we remove the edges of the triangulation in each pocket \(P_i\). This leaves us with edges of \(\varDelta (P)\) that bound the \(P_i\) and a set of Steiner points on them. We call the piece of an edge between two consecutive Steiner points \(p_i p_{i+1}\) an interval.

Definition 2

We call a pair of intervals \(p_j p_{j+1}\), \(q_l q_{l+1}\) weakly visible if and only if there exists at least one pair of points \(w \in p_j p_{j+1}\) and \(z \in q_l q_{l+1}\), such that w and z are visible to each other.

If a pair of intervals \(p_j p_{j+1}\) and \(q_l q_{l+1}\) of a pocket \(P_i\) are weakly visible, but either one of the endpoints of \(p_j p_{j+1}\) is not visible to either one of the endpoints of \(q_l q_{l+1}\), then we find a pair of points \(p_{\alpha } \in p_j p_{j+1}\) and \(q_{\alpha } \in q_l q_{l+1}\) that are visible to each other and add \(p_{\alpha }\) and \(q_{\alpha }\) in the set of Steiner points. We connect \(p_{\alpha }\) and \(q_{\alpha }\) with an arc and add the two points to V and the arc to E.

Definition 3

An arc \(e \in E\) is called a good arc if and only if \(e \subset int(P) \bigcup \varDelta (P)\).

Definition 4

An arc \(e \in E\) is called a bad arc if and only if \(e \subset \tilde{P}\).

Once we construct G, we add s and t in the set of vertices V and add arcs in E between s (likewise t) and the Steiner points on the edges of the face that contains s (likewise t).

Lemma 6

G has \(O(n^2 \sigma ^2)\) vertices and edges. G can be constructed in \(O(n^2 \sigma ^2)\) time.

Proof

To construct the good arcs of G, we connect all pair of Steiner points p and q if and only if p and q are adjacent Steiner points on the same edge of a face \(f_i\) in P or p and q are placed on two different edges of \(f_i\). The weight of the arc (pq) is the length of the arc.

For the set of bad arcs, in a pocket \(P_i\), we check for every pair of Steiner points p, q on the edges of \(\varDelta (P_i)\), where \(\varDelta (P_i)\) are the edges of \(\varDelta (P)\) that bound \(P_i\), if p and q are visible to each other. As mentioned in Sect. 4.3, there may be cases when for a pair of intervals \(p_j p_{j+1}\) and \(q_l q_{l+1}\), none of the endpoints of \(p_j p_{j+1}\) is visible from \(q_r q_{r+1}\), but \(\pi _k(s,t)\) passes through points \(o_j \in p_j p_{j+1}\) and \(o_l \in q_r q_{r+1}\). To resolve this issue we check the visibility of every interval \(p_j p_{j+1}\) from every other \(q_r q_{r+1}\) on the edges of \(\varDelta (P_i)\). So if at least one endpoint of \(p_j p_{j+1}\) is visible to at least one endpoint of \(q_r q_{r+1}\), we connect the visible Steiner points with arcs known as bad arcs. Otherwise, we check for weak visibility between \(p_j p_{j+1}\) and \(q_r q_{r+1}\). If there exists at least one pair of points \(p_l \in p_j p_{j+1}\) and \(q_l \in q_r q_{r+1}\) such that \(p_l\) and \(q_l\) are visible to each other, we connect \(p_l\) and \(q_l\) with a bad arc and add \(p_l\) and \(q_l\) to the set of vertices of G. Such newly created Steiner points are called visibility Steiner points. Since there are \(O(\sigma )\) Steiner points in each edge of \(\varDelta (P_i)\), and there exist \(n_i\) such edges, if \(n_i\) is the number of vertices of \(P_i\), there exist \(O(n_i \sigma )\) Steiner points. Hence there can be at most \(O(n_i \sigma )\) intervals on the edges of \(\varDelta (P_i)\). Weak visibility polygon of an interval \(p_j p_{j+1}\) of \(P_i\) can be constructed in \(O(n_i \sigma )\) time [5], where we consider the Steiner points to be the vertices of the weak visibility polygon. Now, for every interval \(p_j p_{j+1}\) we can construct its weak visibility polygon and check if \(p_j p_{j+1}\) is weakly visible from every other interval \(q_r q_{r+1}\) in \(P_i\). We obtain the pair of visibility Steiner points \(p_l\) and \(q_l\) that are visible to each other, similarly and connect them with a bad arc. Note that, one of the visibility Steiner points \(p_l\) and \(q_l\) can possibly be one endpoint of an existing interval. An interval \(p_j p_{j+1}\) may be weakly visible to \(O(n_i \sigma )\) other intervals on \(\varDelta (P_i)\) for which we may have to introduce \(O(n_i \sigma )\) new pairs of visibility Steiner points and connect them with bad arcs and assign their lengths as their weights. Hence our procedure creates \(O(n_i^2 \sigma ^2)\) visibility Steiner points in \(P_i\). Whenever a pair of visibility Steiner points is added to G a bad arc is also added to G. Therefore, there can be \(O(n_i^2 \sigma ^2)\) bad arcs in \(P_i\). Therefore it takes \(O(n_i^2 \sigma ^2)\) time to add the bad arcs for every pair of intervals in \(P_i\). Since \(\sum n_i \le n\), in \(O(n^2 \sigma ^2)\) time the set of Steiner points and bad arcs can be added to G. \(\blacksquare \)

Let \(\pi ^{**}_k(s,t)\) be the shortest path in G with at most k bad arcs, computed using a modified version of Dijkstra’s algorithm proposed in [14] called Dijkstra’s-k-violation algorithm.

Let the optimal k-violation shortest path \(\pi _k(s,t)\) pass through a sequence of edges \(e_{\alpha _1}, e_{\alpha _2}, \ldots , e_{\alpha _l}\). In each edge \(e_{\alpha _j}\), \(\pi _k(s,t)\) passes through a point \(o_j\) between two Steiner points \(a_{\alpha _j}, b_{\alpha _j}\). Therefore, \(\pi _k(s,t) = [s,o_1,o_2, \ldots , o_l, t]\).

Now, let us construct a path \(\pi ^*_{k}(s,t)\), just as we did in Sect. 4.2. In each edge \(e_{\alpha _j}\), we assign to \(u_{\alpha _j}\) the Steiner point or visibility Steiner point that is closer to \(o_j\) and is an endpoint of a bad arc, among the pair \(a_{\alpha _j}, b_{\alpha _j}\). Let \(\pi ^*_{k}(s,t) = [s,u_{\alpha _1},u_{\alpha _2},\ldots ,u_{\alpha _l},t]\).

Lemma 7

For any edge \(o_s o_{s+1}\) of \(\pi _k(s,t)\) in a pocket \(P_i\), such that \(o_s \in p_i p_{i+1}\) and \(o_{s+1} \in q_j q_{j+1}\), the length of the line segment connecting one endpoint of \(p_i p_{i+1}\) to one endpoint of \(q_j q_{j+1}\) is at most \((1+2\epsilon ) \cdot |o_s o_{s+1}|\).

Proof

Observe that, in each pocket \(P_i\), for a pair of intervals \(p_i p_{i+1}, q_j q_{j+1}\) that are visible, weakly or totally, one of the following two cases are possible. Either, at least one of the endpoints of the interval \(p_i p_{i+1}\) is visible to at least one of the endpoints of the interval \(q_j q_{j+1}\) or there exists a point \(p_l \in p_i p_{i+1}\) that is visible to \(q_l \in q_j q_{j+1}\). \(p_l\) and \(q_l\) are present in the set V of G. Let \(\pi _k(s,t)\) pass the boundary of \(P_i\) through points \(o_s\) and \(o_{s+1}\). If \(o_{s} \in p_i p_{i+1}\) and \(o_{s+1} \in q_j q_{j+1}\) and \(p_i\) is visible to \(q_{j+1}\), then by Lemma 4, \(|p_i q_{j+1}|\le (1+2\epsilon ) \cdot |o_s o_{s+1}|\). If \(o_s \in p_i p_l\) and \(o_{s+1} \in q_j q_l\), then we have \(|p_l q_l| \le (1+2\epsilon ) \cdot |o_s o_{s+1}|\) as well, since \(p_l \in p_i p_{i+1}\) and \(q_l \in q_j q_{j+1}\), hence \(|p_l o_s| \le |p_i o_s|\) and \(|q_l o_{s+1}| \le |q_j o_{s+1}|\). We assign \(p_l\) to \(u_{\alpha _l}\). \(\blacksquare \)

Lemma 8

\(\pi ^*_k(s,t) \le (1+2\epsilon ) \cdot \pi _k(s,t)\).

Proof

From Lemma 7, the length a bad arc in any pocket \(P_i\), connecting the endpoints of the intervals through which \(\pi _k(s,t)\) passes, is at most \((1+2\epsilon )\) times the length of the path segment of \(\pi _k(s,t)\) in \(P_i\). Rest of \(\pi ^*_{k}(s,t)\) is constructed exactly as we constructed \(\pi ^*(s,t)\) of Sect. 4.2 and Lemma 4. \(\blacksquare \)

Lemma 9

Let \(\pi ^{**}_k\) be the path in G computed by Dijkstra’s-k-violation algorithm [14]. Then \(\pi ^{**}_k(s,t) \le (1+2\epsilon ) \cdot \pi _k(s,t)\).

Proof

\(\pi ^*_k(s,t)\) is a path in G. Since \(\pi ^{**}_k\) is the path produced by Dijkstra’s-k-violation algorithm, therefore \(\pi ^{**}_k \le \pi ^*_k\). By Lemma 8, \(\pi ^*_k(s,t) \le (1+2\epsilon )\cdot \pi _k(s,t)\). Therefore, \(\pi ^{**}_k(s,t) \le (1+2\epsilon ) \cdot \pi _k(s,t)\). \(\blacksquare \)

Theorem 2

The \((1+\epsilon )\)-factor approximate k-violation shortest path between any pair of points s and t can be computed in \(O(n^2 \sigma ^2 k \log n^2 \sigma ^2 + n^2 \sigma ^2 k)\) on G, where \(\sigma = O(\log _\delta (\frac{|L|}{r}))\).

Proof

Since G consists at most \(O(n^2 \sigma ^2)\) vertices and \(O(n^2 \sigma ^2)\) arcs (by Lemma 6) and \(\pi ^{**}_k(s,t) \le (1+2\epsilon ) \cdot \pi _k(s,t)\) (by Lemma 9), the time complexity is the same as computing single source shortest path with at most k bad edges on a graph with as many vertices and arcs with Dijkstra’s-k-violation algorithm [14]. \(\blacksquare \)

6 Conclusion

In this paper, we studied the shortest k-violation path problem in polygons. We produced a \((1+\epsilon )\)-factor algorithm for the problem that runs in \(O(n^2 \sigma ^2 k\log n^2 \sigma ^2 + n^2 \sigma ^2 k)\) time, where \(\sigma = O(\log _\delta (\frac{|L|}{r}))\). We show that when \(k=1\) and pockets of polygon P are convex, a \((1+\epsilon )\)-factor approximate shortest one violation path can be computed in \(O(n \sigma \log n \sigma + n \sigma ^2 )\) time. A k-violation path is allowed to bend only in the interior of a polygon P. It will be interesting to see whether an algorithm can be designed to compute a \((1+\epsilon )\)-factor shortest k-violation path in sub-quadratic time.