Improved Approximation of Two Watchmen’s Routes in Simple Polygons

For three distinct indices $i$, $i^{\prime }$, and $i^{\prime \prime }$, we have that $i\prec i^{\prime }\prec i^{\prime \prime }$ if one of the following sequences of inequalities holds: , or , or , i.e., there exists a boundary point on $P$ such that a clockwise traversal of the boundary starting at this point reaches the bottom points of the windows in the order $C_i$, $C_{i^{\prime }}$, $C_{i^{\prime \prime }}$​.

Assume that there are indices $i_1\prec j_1\prec i_2\prec j_2\prec i_1\prec j_1$ such that $T_s^{\text{1}}$ intersects $C_{i_1}$ and $C_{i_2}$, but not $C_{j_1}$ and $C_{j_2}$, and $T_{s^{\prime }}^{\text{1}}$ intersects $C_{j_1}$ and $C_{j_2}$, but not $C_{i_1}$ and $C_{i_2}$. Consider the polygonal chain defined by the part of $C_{i_1}$ between its bottom point and its intersection with $T_s^{\text{1}}$, the part of $T_s^{\text{1}}$ until its intersection with $C_{i_2}$, and the part of $C_{i_2}$ until its top point; see Figure 3. This chain separates $P$ into two regions. By definition, $s$ lies in one of these regions $P_s$. As $T_s^{\text{1}}$ does not visit $C_{j_1}$, the window $C_{j_1}$ lies in the other region, ${\overline{P}}_s=P\setminus P_s$. Let ${\widehat{P}}_s\subseteq {\overline{P}}_s$ be the region enclosed by $C_{i_1}$, $C_{i_2}$, $T_s^{\text{1}}$, and, if $C_{i_1}$ and $C_{i_2}$ do not intersect, possibly part of the polygon boundary; see Figure 3(b). The region ${\widehat{P}}_s$ may be empty; see Figure 3(a) for such an example. Since $s^{\prime }$ lies outside the visibility polygons associated to the four windows we consider, $s^{\prime }$ either lies in $P_s$ or in ${\widehat{P}}_s$.

If $s^{\prime }$ lies in $P_s$, then $T_{s^{\prime }}^{\text{1}}$ has to cross $C_{i_1}$ or $C_{i_2}$ in order to visit $C_{j_1}$, contradicting the stated assumptions; see Figures 3(a) and (b). If $s^{\prime }$ lies in ${\widehat{P}}_s$, then in order for $T_{s^{\prime }}^{\text{1}}$ to visit $C_{j_2}$, it must cross the boundary of ${\widehat{P}}_s$, again contradicting our stated assumptions. Hence, $T_s^{\text{1}}$ (and $T_{s^{\prime }}^{\text{1}}$) visits an ordered subsequence of the windows as stated. $◀$ The previous lemma gives us an immediate algorithm to compute $T_s^{\text{1}}$ and $T_{s^{\prime }}^{\text{1}}$. By trying every index pair $0\le i,j\le |{𝒮}_1|-1$, computing the shortest route starting at $s$ that visits the windows $C_i,C_{i+1},\mathrm{\dots },C_{j-1}$ and the shortest route starting at $s^{\prime }$ that visits the windows $C_j,C_{j+1},\mathrm{\dots },C_{i-1}$, indices always taken modulo |${𝒮}_1$|, and selecting the min-max shortest pair of these, we obtain the two desired routes $V_s^{\text{1}}=T_s^{\text{1}}$ and $V_{s^{\prime }}^{\text{1}}=T_{s^{\prime }}^{\text{1}}$. There are $O(m^2)$ index pairs, and computing the shortest route takes $O(m^{3}n)$ for each of these pair, as described in Section 2. Thus, the time complexity is bounded by $O(m^{5}n)$. We state this result as a theorem.

Consider the point $p_i\in {𝒮}_2$. Both windows $C_s^i$ and $C_{s^{\prime }}^i$ of $\text{VP}(p_i)$ intersect $\text{SP}(s,s^{\prime })$. Without loss of generality assume that $t_s^{p_i}=t_{\min }^{p_i}$, the other case is proved in the same way.

If $C_s^i$ intersects the subpath $\text{SP}(s,p_B)$, where $p_B$ is the point at distance $B$ from $s$ along $\text{SP}(s,s^{\prime })$, then $C_s^i$ intersects the funnel $F_s^B$ and the lemma holds. If $C_s^i$ does not intersect the subpath $\text{SP}(s,p_B)$, then it intersects the subpath $\text{SP}(s^{\prime },p_B)$ at $p_x$; see Figure 4(b). The pseudotriangle bounded by $t_s^{p_i}$, $C_s^i$, and $\text{SP}(s,p_x)$ must have an acute angle at $p_x$, since the angle between $t_s^{p_i}$ and $C_s^i$ is right or obtuse. Therefore, $C_s^i$ must intersect the geodesic half circle $H_s^B$, since $\Vert t_s^{p_i}\Vert \le B$ and $t_s^{p_i}$ is a subpath of one of the paths $F_s^B=\{\text{SP}(s,p)\mid p\in H_s^B\}$, hence $\text{VP}(p_i)$ intersects $F_s^B$ also in this case. $◀$ Next, we compute an initial solution for which we can bound the min-max length. Let ${𝒮}_s^{\text{std}}$ and ${𝒮}_{s^{\prime }}^{\text{std}}$ be a partitioning of the points in ${𝒮}_2$ that we obtain as follows. If for a point $p_i\in {𝒮}_2$ $\Vert t_s^{p_i}\Vert \le \Vert t_{s^{\prime }}^{p_i}\Vert$, then $p_i$ belongs to ${𝒮}_s^{\text{std}}$, otherwise $p_i$ belongs to ${𝒮}_{s^{\prime }}^{\text{std}}$​. We call this the standard partitioning of the points in ${𝒮}_2$. It follows from Lemma 4 that each visibility polygon $\text{VP}(p_i)$, for every $p_i\in {𝒮}_2$, is at distance at most $B$ from one of $s$ or $s^{\prime }$​.

Let $V_s^{\text{std}}$ and $V_{s^{\prime }}^{\text{std}}$ be the two shortest routes that see the points in ${𝒮}_s^{\text{std}}$ and ${𝒮}_{s^{\prime }}^{\text{std}}$, respectively, that we can compute with the modified method of Tan and Jiang [11].

Consider the boundary of the funnel $F_s^B$​. It consists of two paths of length $B$ and a sequence of connecting arcs of circles having radius at most $B$; the sum of their lengths is bounded by $\pi B$. The perimeter is a route that intersects all the visibility polygons of the points in ${𝒮}_s^{\text{std}}$. Since $V_s^{\text{std}}$ is the shortest route that intersects these visibility polygons, its length is bounded by $(2+\pi )B$. The length of the perimeter of $F_{s^{\prime }}^B$ is bounded in the same way and since $\text{OPT}\ge 2B$, the lemma follows. $◀$ Next, we improve on the previous result by updating the standard partitioning and obtain a $(1+\epsilon )$-approximation, for any $\epsilon >0$. We consider $\epsilon$ to be a constant, sufficiently small, and define the integer $k=\lceil 69/\epsilon \rceil$.

We partition the points into two sets in such a way that for each point the shortest path from the corresponding starting point is within a $(1+\epsilon )$ factor from the optimum. In order to do this, we make a decomposition of the points in ${𝒮}_2$ into few subsets such that those points for which their corresponding windows are “similar” are placed in the same subset. By then choosing one representative point from each subset, we can compute the optimal partition of them using brute force, since there are only a few points to partition. The partition of the representative points indicates in which partition each similar point should be in. Once the partition for the full set of points has been computed, we can compute the two shortest watchman routes using the algorithm described in Section 2. We provide the details of the construction below.

For any point $p_i\in {𝒮}_2$ where $\Vert t_{\max }^{p_i}\Vert >3B$, we can immediately assume that $p_i$ must be seen by the route from the starting point for which the geodesic is shorter. Otherwise, $\text{OPT}>6B$, as the optimal route must at least be as long as the geodesic $t_{\max }^{p_i}$, followed to $\text{VP}(p_i)$ and back. In this case, the standard partitioning together with the optimal routes for ${𝒮}_1$, i.e., the solution $(V_s^{\text{1}}\cup V_s^{\text{std}},V_{s^{\prime }}^{\text{1}}\cup V_{s^{\prime }}^{\text{std}})$ gives at worst a $2$-approximation to our problem, since . Let ${𝒮}_2^{\text{L}}$ be the subset of the points in ${𝒮}_2$ for which $t_{\max }^{p_i}$ is “too long”, in particular, $\Vert t_{\max }^{p_i}\Vert >3B$, and assume they are partitioned according to the starting point of their shorter geodesic $t_{\min }^{p_i}$. Furthermore, let ${𝒮}_2^{\text{S}}={𝒮}_2\setminus {𝒮}_2^{\text{L}}$ be the remaining points in ${𝒮}_2$ for which $t_{\max }^{p_i}$ is “short”. It remains to find an appropriate partition of the points in ${𝒮}_2^{\text{S}}$. To do this, we define a refinement of the funnel, and partition it into $k^2$ cells.

Define $r\stackrel{\text{def}}{=}\min \{3B,\Vert \text{SP}(s,s^{\prime })\Vert /2\}$. For the points $p_i\in {𝒮}_2^{\text{S}}$, we have $\Vert t_{\max }^{p_i}\Vert \le r$ by definition, giving us that $\Vert t_s^{p_i}\Vert ,\Vert t_{s^{\prime }}^{p_i}\Vert \le r$. Let $F_s^r$ and $F_{s^{\prime }}^r$ be the two funnels of radius $r$ from $s$ and $s^{\prime }$, respectively.

We make a similarity decomposition of the set of points in ${𝒮}_2^{\text{S}}$ into at most $k^4$ distinct subsets ${𝒮}_2^{\text{(1)}},{𝒮}_2^{\text{(2)}},\mathrm{\dots },{𝒮}_2^{\text{(}{k}^4\text{)}}$ as follows. $H_s^r$ is the geodesic half circle of radius $r$ centered at $s$; see Figure 5(a). Consider the $k+1$ consecutive equidistant points $h_j$, for $0\le j\le k$, along $H_s^r$, $h_0$ and $h_k$ being the two endpoints of $H_s^r$. The points of $F_s^r$ between the two geodesics $\text{SP}(s,h_{j-1})$ and $\text{SP}(s,h_j)$, for each $1\le j\le k$, define a subfunnel of $F_s^r$, denoted $F_s^r(j)$, lightly shaded in Figure 5(a). We can further decompose each subfunnel $F_s^r(j)$ into $k$ cells , for $1\le j^{\prime }\le k$, depending on the distance to $s$. A cell $c_s^{j,j^{\prime }}$ is more heavily shaded in Figure 5(a). The funnel $F_s^r$ thus decomposes into $k^2$ cells. Similarly, we decompose the funnel $F_{s^{\prime }}^r$ into $k^2$ cells $c_{s^{\prime }}^{j,j^{\prime }}$, for $1\le j,j^{\prime }\le k$.

We say that a window $C_s^i$ belongs to cell $c_s^{j,j^{\prime }}$ if the intersection point of $t_s^{p_i}$ and $C_s^i$ is a point in the cell $c_s^{j,j^{\prime }}$. The point $p_i\in {𝒮}_2^{\text{S}}$ lies in the subset ${𝒮}_2^{\text{(}\kappa \text{)}}$ if $C_s^i$ belongs to $c_s^{j_s,j_s^{\prime }}$​, $C_{s^{\prime }}^i$ belongs to $c_{s^{\prime }}^{j_{s^{\prime }},j_{s^{\prime }}^{\prime }}$​, and $\kappa =j_s+(j_s^{\prime }-1)k+(j_{s^{\prime }}-1)k^2+(j_{s^{\prime }}^{\prime }-1)k^3$​. In this way we have partitioned all the points in ${𝒮}_2^{\text{S}}$ into at most $k^4$ distinct subsets.

For each non-empty subset, we select one point as the representative for the subset and let $ℛ\subseteq {𝒮}_2^{\text{S}}$ be the set of all the chosen representative points. By trying all $2^{|ℛ|}\le 2^{k^4}$ partitions of the representative points of $ℛ$ into two subsets, we compute the two shortest tours $V_s^x$ and $V_{s^{\prime }}^x$ that visit the visibility polygons of the points in $ℛ\cup {𝒮}_2^{\text{L}}$, over all possible partitions of $ℛ$.

Let $V_s^{\text{ref}}$ and $V_{s^{\prime }}^{\text{ref}}$ be the two shortest routes obtained from the partition given by placing each point in a subset ${𝒮}_2^{\text{(}\kappa \text{)}}$ in the same partition as the representative point of this subset. The two routes can be computed in $O(m^{3}n)$ time. To bound the lengths of $V_s^{\text{ref}}$ and$V_{s^{\prime }}^{\text{ref}}$, we introduce two auxiliary routes $V_s^{\epsilon }$ and $V_{s^{\prime }}^{\epsilon }$ that are easier to bound and prove that $V_s^{\text{ref}}$ and $V_{s^{\prime }}^{\text{ref}}$ are not longer than $V_s^{\epsilon }$ and $V_{s^{\prime }}^{\epsilon }$, respectively.

Let $d=\max \{\Vert V_s^x\Vert ,\Vert V_{s^{\prime }}^x\Vert \}$. We construct the route $V_s^{\epsilon }$ from $V_s^x$ as follows ($V_{s^{\prime }}^{\epsilon }$ is constructed from $V_{s^{\prime }}^x$ in the same way). Let $d_{\max }$ be the supremum value for which the geodesic half circle $H_s^{d_{\max }}$ intersects $V_s^x$​, i.e., $d_{\max }={sup}_{L>0}\left\{H_s^L\cap V_s^x\ne \mathrm{\varnothing }\right\}$. Let $p$ be a point of contact between $H_s^{d_{\max }}$ and a convex vertex of $V_s^x$; see Figure 5(b). From $p$ follow $V_s^x$ in counterclockwise order until a reflex vertex $v_0$ of $V_s^x$ is encountered. From $p$ now follow $V_s^x$ in clockwise order until a reflex vertex $v_{l+1}$ of $V_s^x$ is encountered, where $l$ is the number of convex vertices on the clockwise path of $V_s^x$ from $v_0$ to $v_{l+1}$. Let $p_{d_{\max }}$ be the point of intersection of $H_s^{d_{\max }}$ and $\text{SP}(s,s^{\prime })$ and let $\theta$ be the angle between the tangent of $H_s^{d_{\max }}$ at $p_{d_{\max }}$ and the $x$-axis. For simplicity of construction, assume $P$​, $F_s^{d_{\max }}$, and $V_s^x$ to be rotated so that $\theta =\pi /2$, i.e., the tangent of $H_s^{d_{\max }}$ at $p_{d_{\max }}$ is vertical. Let $v_{l^{\ast }}$, for some $1\le l^{\ast }\le l$, be the vertex of $V_s^x$ such that the edges $[v_{l^{\ast }-1},v_{l^{\ast }}]$ and $[v_{l^{\ast }},v_{l^{\ast }+1}]$ lie on the same side of a vertical line through $v_{l^{\ast }}$, i.e., the rightmost vertex of $V_s^x$, if $s$ lies locally to the left and $s^{\prime }$ lies locally to the right of $p_{d_{\max }}$. For some $1\le l_U\le l^{\ast }$, assume the edges $[v_{\lambda -1},v_{\lambda }]$ have non-negative slope, for all $1\le \lambda \le l_U$. Similarly, for some $l^{\ast }\le l_D\le l$, assume the edges $[v_{\lambda },v_{\lambda +1}]$ have non-positive slope, for all $l_D\le \lambda \le l$. Let the clockwise subpath from $s$ to $v_{l_U}$ of $V_s^x$ also be the first part of $V_s^{\epsilon }$. Add a vertical edge of length $(5r+4d)/k$ at $v_{l_U}$ upward to a new vertex $v_{l_U}^{\prime }$ and a vertical edge of length $(5r+4d)/k$ at $v_{l_D}$ downward to a new vertex $v_{l_D}^{\prime \prime }$. While , the segment $[v_{\lambda },v_{\lambda +1}]$ has slope angle ${\theta }_{\lambda }$, and we offset the segment by a distance $(5r+4d)/k$ in the direction ${\theta }_{\lambda }+\pi /2$ (increasing angles going clockwise around a circle), which gives the segment $[v_{\lambda }^{\prime \prime },v_{\lambda +1}^{\prime }]$; see Figures 5(b) and (c). We connect $v_{\lambda }^{\prime }$ with $v_{\lambda }^{\prime \prime }$ by a circle arc with origin $v_{\lambda }$ and radius $(5r+4d)/k$, for each $l_U\le \lambda \le l_D$ and finally connect $v_{l_D}$ back to $s$ with the corresponding subpath of $V_s^x$; again see Figures 5(b) and (c). If at some point the construction intersects the polygon boundary we shortcut the path so that it is the shortest to connect to in the free space of the polygon. We show that $(V_s^{\epsilon },V_{s^{\prime }}^{\epsilon })$ sees all points in ${𝒮}_2$ and bound the min-max length.

Recall that $(T_s,T_{s^{\prime }})$ is an optimal min-max solution to the shortest two-watchman route problem for the points in $𝒮$, and let $(T_s^{\text{2}},T_{s^{\prime }}^{\text{2}})$ be an optimal min-max solution for the points in ${𝒮}_2$. Since $(V_s^x,V_{s^{\prime }}^x)$ is an optimal min-max solution for the problem on the points in $ℛ\cup {𝒮}_2^{\text{L}}\subseteq {𝒮}_2$, it follows that $\Vert V_s^x\Vert \le \Vert T_s^{\text{2}}\Vert \le \Vert T_s\Vert \le \text{OPT}$ and $\Vert V_{s^{\prime }}^x\Vert \le \Vert T_{s^{\prime }}^{\text{2}}\Vert \le \Vert T_{s^{\prime }}\Vert \le \text{OPT}$, whereby $d\le \text{OPT}$.

Let $p_i$ be a point in $ℛ\cap {𝒮}_2^{\text{(}\kappa \text{)}}$, for some $\kappa$, $1\le \kappa \le k^4$, and assume that $V_s^x$ sees $p_i$. This implies that $V_s^x$ intersects the window $C_s^i$ at some point $p$. Consider any other point $p_j$ in the same subset ${𝒮}_2^{\text{(}\kappa \text{)}}$ as $p_i$. Since the endpoints of $t_s^{p_i}$ and $t_s^{p_j}$ lie in the same cell, the angle between the windows $C_s^i$ and $C_s^j$ is at most $\pi /k$ and the distance between the two windows within the cell is at most $(1+\pi )r/k$ as this is an upper bound on the farthest distance between any two points in a cell (the height of the cell plus the width of the cell); see Figure 6. Let ${\widehat{p}}_i$ be the endpoint of $t_s^{p_i}$ intersecting the window $C_s^i$. Thus, the distance from $p$ to $C_s^j$ is bounded by

Hence, if $V_s^x$ sees $p_i$, then $V_s^{\epsilon }$ sees all points in ${𝒮}_2^{\text{(}\kappa \text{)}}$ as $p_j$ was chosen arbitrarily in ${𝒮}_2^{\text{(}\kappa \text{)}}$​. We can argue the other possibility when $V_{s^{\prime }}^x$ sees $p_i$ in the same way and therefore, since $V_s^x$ and $V_{s^{\prime }}^x$ see all representative points in $ℛ$, $V_s^{\epsilon }$ and $V_{s^{\prime }}^{\epsilon }$ together see all points in ${𝒮}_2$.

It remains to bound the lengths of $V_s^{\epsilon }$ and $V_{s^{\prime }}^{\epsilon }$. We do this only for $V_s^{\epsilon }$ as the argument for $V_{s^{\prime }}^{\epsilon }$ is the same. $V_s^{\epsilon }$ consists of translated segments from $V_s^x$ (recall that $\Vert V_s^x\Vert \le d$), two additional segments of length $(5r+4d)/k$, and circular arcs, also of radius $(5r+4d)/k$, where the angle sum is at most $\pi$; see Figures 5(b) and (c). The total length of $V_s^{\epsilon }$ is therefore bounded by

as claimed. $◀$

We summarize the results on handling the points in ${𝒮}_2$.

By construction, the routes $V_s^{\text{ref}}$ and $V_{s^{\prime }}^{\text{ref}}$ visit the same windows as the routes $V_s^{\epsilon }$ and $V_{s^{\prime }}^{\epsilon }$  respectively. As $V_s^{\text{ref}}$ and $V_{s^{\prime }}^{\text{ref}}$ are the shortest routes that visit the windows in this way, $\Vert V_s^{\text{ref}}\Vert \le \Vert V_s^{\epsilon }\Vert$ and $\Vert V_{s^{\prime }}^{\text{ref}}\Vert \le \Vert V_{s^{\prime }}^{\epsilon }\Vert$. Since $r\le 3B\le 3\text{OPT}/2$ and $d\le \text{OPT}$, we obtain

by our choice of $k$. Moreover, we can compute $V_s^{\text{ref}}$ and $V_{s^{\prime }}^{\text{ref}}$ in $O(m^{3}n)$ time, as mentioned in Section 2. $◀$