# Multirobot Watchman Routes in a Simple Polygon

Joseph S. B. Mitchell Linh Nguyen Department of Applied Mathematics and
Statistics, Stony Brook University<EMAIL_ADDRESS>of Applied Mathematics and Statistics, Stony Brook University,
<EMAIL_ADDRESS>
###### Abstract

The well-known Watchman Route problem seeks a shortest route in a polygonal
domain from which every point of the domain can be seen. In this paper, we
study the cooperative variant of the problem, namely the $k$-Watchmen Routes
problem, in a simple polygon $P$. We look at both the version in which the $k$
watchmen must collectively see all of $P$, and the quota version in which they
must see a predetermined fraction of $P$’s area.

We give an exact pseudopolynomial time algorithm for the $k$-Watchmen Routes
problem in a simple orthogonal polygon $P$ with the constraint that watchmen
must move on axis-parallel segments, and there is a given common starting
point on the boundary. Further, we give a fully polynomial-time approximation
scheme and a constant-factor approximation for unconstrained movement. For the
quota version, we give a constant-factor approximation in a simple polygon,
utilizing the solution to the (single) Quota Watchman Route problem.

##  1 Introduction

In 1973, Victor Klee introduced the Art Gallery problem: given an art gallery
with $n$ walls (a polygon $P$), determine the minimum number of stationary
guards at points within $P$ such that every point of $P$ can be seen by at
least one guard point. The Art Gallery problem and its many variants have
since been the subject of a large body of research in computational geometry
and algorithms.

When guards are mobile, a single guard suffices to see a connected domain;
thus, we are interested in finding routes for one or more guards that optimize
some aspects of the guard(s)’ movement (e.g., path lengths, the number of
turns, etc). The problem of minimizing the distance that one guard must travel
to see the entire polygon is the Watchman Route problem (WRP). Chin and Ntafos
[3] introduced the WRP, proved NP-hardness in polygons with holes (see [6])
and gave an $O(n)$ algorithm for simple orthogonal polygons. In (general)
simple polygons, there are exact polynomial-time algorithms; the current best
running times are $O(n^{3}\log n)$ for the anchored version (a starting point
$s$ which the route must pass through is given) and $O(n^{4}\log n)$ for the
floating version (no starting point is given) [5].

In some settings, complete coverage might not be feasible or necessary, thus
we are also interested in computing a shortest route that sees at least an
area of $A\geq 0$ within $P$. This is known as the Quota Watchman Route
problem (QWRP), introduced in [8]. In contrast to the tractable WRP, the QWRP
is (weakly) NP-hard, but a fully polynomial-time approximation scheme (FPTAS)
is known. Any results about the QWRP can be adapted to the WRP by simply
letting $A$ be equal to the area of $P$.

We consider the generalization to multiple agents of both the WRP and the
QWRP, namely the $k$-Watchmen Routes problem ($k$-WRP) and the Quota
$k$-Watchmen Routes problem (Q$k$-WRP), with the objective of minimizing the
length of the longest path traveled by any one watchman. Even in a simple
polygon, when no starting points are specified (so, we are to determine the
best starting locations), both problems are NP-hard to approximate within any
multiplicative factor [12].

We thus focus on the (boundary) anchored version, in which a team of robots or
searchers enter a domain $P$ through a door on its boundary to search for a
stationary target, which may be randomly distributed within the domain; the
objective is to plan for an optimal collective effort to guarantee at least a
certain probability of detection (1 in the $k$-WRP and some $p\in[0,1]$ in the
Q$k$-WRP). We consider the number, $k$, of robots to be fixed and relatively
small, as in most practical situations it is infeasible to employ arbitrarily
many watchmen/robots/agents. We present, for any fixed $k$, a
pseudopolynomial-time (polynomial in the number $n$ of vertices of $P$ and the
length of the longest edge of $P$) exact algorithm to solve the anchored
$k$-WRP in a simple orthogonal (integral coordinate) polygon $P$ under L1
distance. The pseudopolynomial-time exact algorithm is the basis for the FPTAS
for L1 distance and the $(\sqrt{2}+\varepsilon)$-approximation for L2
distance. For the Q$k$-WRP, we give polynomial-time constant-factor
approximations in a simple polygon. While we restrict ourselves to the
anchored version, we achieve better approximation factors for any (fixed) $k$
than the ones Nilsson and Packer proposed for the case $k=2$ in [11].

##  2 Preliminaries

Let $P$ be a simple polygon, i.e. a simply connected subset of
$\mathbb{R}^{2}$. Denote by $\partial P$ the boundary of $P$, a polygonal
chain that does not self-intersect consisting of $n$ vertices
$v_{1},v_{2},\ldots,v_{n}$, which we assume to have integer coordinates. A
simple polygon is orthogonal if the internal angle at every vertex is either
90 (convex vertex) or 270 degrees (reflex vertex).

For a point $x\in P$, its visibility region, denoted by $V(x)$, is the set of
all points $y$ such that the segment $xy$ does not intersect with the exterior
of $P$: we say $x$ and $y$ and see each other. For an arbitrary set
$X\subseteq P$, the visibility region of $X$, $V(X)$, is the set of all points
that are seen by some point in $X$. When $X$ is either a point or a line
segment, $V(X)$ is necessarily a simple subpolygon of $P$ with at most $n$
vertices and can be computed in $O(n)$ time [7, 13]. We use $|\cdot|$ to
denote Euclidean measure of geometric objects (e.g., length or area).

The first problem we investigate is the anchored $k$-WRP, where the polygon
$P$ is orthogonal and movements of the watchmen are rectilinear (L1 distance).
Given a simple orthogonal polygon $P$ and a starting point $s\in\partial P$,
we compute $k$ tours $\\{\gamma_{i}\\}$ within $P$ consisting of horizontal
and vertical segments, all starting from $s$ such that
$\bigcup\limits_{i=1,\ldots,k}V(\gamma_{i})=P$ and
$\max\limits_{i=1,\ldots,k}|\gamma_{i}|$ is minimized. We also assume that the
coordinates of the vertices of $P$ are integers. It is known that even for
$k=2$, the general $k$-WRP in a simple polygon is (weakly) NP-hard via a
simple reduction from Partition [10]. The reduction can be easily modified to
show that our version is also NP-hard. The second problem, Q$k$-WRP,
generalizes the first to
$\left|\bigcup\limits_{i=1,\ldots,k}V(\gamma_{i})\right|\geq A$ for some
$0\leq A\leq|P|$. The fraction of area seen, $\frac{A}{|P|}$, can be
interpreted as the probability that the watchmen detect a target uniformly
distributed in $P$. We consider the Q$k$-WRP in a simple polygon, where the
watchmen have unrestricted movement (not limited to horizontal and vertical).

##  3 $k$-Watchmen in a Simple Orthogonal Polygon

### Dynamic programming exact algorithm

A visibility cut $c_{i}$ with respect to the starting point $s$ is a chord
obtained from extending the edge $e$ incident on a reflex vertex, $v_{i}$,
where $e$ is the edge whose extension creates a convex vertex at $v_{i}$ in
the subpolygon containing $s$. The other subpolygon (not containing $s$) is
the pocket induced by $c_{i}$. Not all reflex vertices induce a visibility
cut. An essential cut is a visibility cut whose pocket does not fully contain
any other pocket (Figure 1). In general, essential cuts may intersect with
each other.

Figure 1: The essential cuts (dashed).

######  Lemma 3.1.

$\bigcup\limits_{i=1,\ldots,k}V(\gamma_{i})=P$ if and only if
$\\{\gamma_{i}\\}$ collectively visit all essential cuts of $P$.

######  Proof 3.2.

The lemma is simply an extension of the well known fact: a single tour sees
all of $P$ if and only if it visits all essential cuts [2, 4, 5].

Denote by $C_{i}$ the set of essential cuts visited by $\gamma_{i}$.

######  Corollary 3.3.

There exists an optimal solution $\\{\gamma_{i}\\}$ such that for any $i$,
$\gamma_{i}$ is the shortest route to visit all cuts in $C_{i}$ and $s$ in the
order in which they appear around $\partial P$.

Consider the decomposition of $P$ into rectangular cells by the maximal
(within $P$) extensions of all edges, as well as a horizontal and vertical
line through $s$; this is known as the Hanan grid (Figure 2).

Figure 2: The Hanan grid formed by extensions of all edges in $P$.

######  Lemma 3.4.

There exists an optimal solution $\\{\gamma_{i}\\}$ within the Hanan grid.

######  Proof 3.5.

Given an optimal solution $\\{\gamma_{i}\\}$, let
$C_{i}=\\{c_{i1},\ldots,c_{ij}\\}$ (in order around $\partial P$) and
$p_{i1},\ldots,p_{ij}$ be the point where $\gamma_{i}$ first makes contact
with $c_{i1},\ldots,c_{ij}$. Denote by $L1_{P}(x,y)$ a geodesic L1 shortest
path between $x$ and $y$, a rectilinear shortest path constrained to stay
within $P$. (For an overview of geodesic shortest paths in both L1 and L2
metrics, see [9].)

First, note that for every $i$, we may replace $\gamma_{i}$ with a
concatenation of geodesic L1 shortest paths, namely
$\gamma_{i}:=L1_{p}(s,p_{i1})\cup L1_{P}(p_{i1},p_{i2})\cup\ldots\cup
L1_{P}(p_{ij},s)$ without increasing
$\max\limits_{i=1,\ldots,k}\\{|\gamma_{i}|\\}$ while maintaining visibility
coverage of $P$.

We argue that $L1_{p}(s,p_{i1})$ is a geodesic L1 shortest path from $s$ to
$c_{i1}$. Suppose to the contrary, that geodesic L1 shortest paths from $s$ to
$c_{i1}$ make contact with $c_{i1}$ at $p^{\prime}_{i1}\neq p_{i1}$ (all
geodesic L1 shortest paths from a point to a segment have the same endpoint).
Due to orthogonality
$|L1_{P}(s,p^{\prime}_{i1})|+|p^{\prime}_{i1}p_{i1}|=|L1_{P}(s,p_{i1})|$,
which means
$|L1_{P}(s,p_{i1})|+|L1_{P}(p_{i1},p_{i2})|=|L1_{P}(s,p^{\prime}_{i1})|+|p^{\prime}_{i1}p_{i1}|+|L1_{P}(p_{i1},p_{i2})|\geq|L1_{P}(s,p^{\prime}_{i1})|+|L1_{P}(p^{\prime}_{i1},p_{i2})|$.
This implies $\gamma_{i}$ should take a geodesic L1 shortest path from $s$ to
$c_{i1}$, and it suffices to find such a path within the Hanan grid. By a
straightforward inductive argument, we can show the same for any portion of
$\gamma_{i}$ between any two essential cuts.

Corollary 3.3 and Lemma 3.4 allow us to reduce the problem to that of finding
a set of grid points on the essential cuts for which each route is
responsible. Then, each route is simply the concatenation of L1 shortest paths
between those points. Let $\\{c_{1},c_{2},\ldots,c_{m}\\}$ be the set of
essential cuts in order around $\partial P$ ($s$ lies between $c_{1}$ and
$c_{m}$). We define each subproblem $(c_{j},p_{1},l_{1},\ldots,p_{k},l_{k})$
by an essential cut $c_{j}$, $k$ Hanan grid points $p_{1},\ldots,p_{k}$ on
essential cuts $c_{1},\ldots,c_{j}$ (and $s$) and $k$ integers
$l_{1},\ldots,l_{k}$. Refer to Figure 3 for an illustration. Subproblem
$(c_{j},p_{1},l_{1},\ldots,p_{k},l_{k})=$ TRUE if and only if there exists a
collection of $k$ paths $\Gamma_{1},\ldots,\Gamma_{k}$ collectively visiting
all essential cuts from $c_{1}$ up to $c_{j}$ such that

  * •

$\Gamma_{i}$ starts at $s$, ends at $p_{i}$,

  * •

$|\Gamma_{i}|=l_{i}$.

Figure 3: An example subproblem $(c_{3},p_{1},l_{1},p_{2},l_{2})$.

The recursion is as follows. For each Hanan grid point $p\in c_{j}$ and
$i=1,\ldots,k$

$\displaystyle\begin{split}&(c_{j},p_{1},l_{1},\ldots,p_{i}:=p,l_{i},\ldots,p_{k},l_{k})\\\
=&\bigvee\limits_{p^{\prime}}(c_{j-1},p_{1},l_{1},\ldots,p_{i}:=p^{\prime},l_{i}-|L1_{P}(p,p^{\prime})|,\ldots,p_{k},l_{k})\end{split}$
(1)

where $p^{\prime}$ is taken from the set of all Hanan grid points on the cuts
$c_{1},\ldots,c_{j-1}$ such that geodesic L1 shortest paths from $p^{\prime}$
to $c_{j}$ make contact with $c_{j}$ at $p$ (Lemma 3.4). The base case is
simply $(s,s,0,\ldots,s,0)=\text{TRUE}$. After tabulating all subproblems, we
take the subproblem $(c_{m},p_{1},l_{1},\ldots,p_{k},l_{k})$ (such that
$(c_{m},p_{1},l_{1},\ldots,p_{k},l_{k})=$ TRUE) with the minimum
$\max\limits_{i=1,\ldots,k}\\{l_{i}+|L1_{P}(p_{i},s)|\\}$ and return the tours
$\\{\gamma_{i}:=\Gamma_{i}\cup L1_{P}(p_{i},s)\\}$.

### Proof of correctness

Our proof of correctness relies on two arguments:

  * •

Since the paths associated with subproblem
$(c_{j-1},p_{1},l_{1},\ldots,p_{i}:=p^{\prime},l_{i}-|L1_{P}(p,p^{\prime})|,\ldots,p_{k},l_{k})$
visit all essential cuts up to $c_{j-1}$, the paths associated with subproblem
$(c_{j},p_{1},l_{1},\ldots,p_{i}:=p,l_{i},\ldots,p_{k},l_{k})$ also visit all
essential cuts up to $c_{j}$ since $p\in c_{j}$. By induction, the tours
returned hence visit all essential cuts.

  * •

$\gamma_{i}$ consists of geodesic L1 shortest paths between contact points
with essential cuts (proof of Lemma 3.4). If we identify two consecutive
contact points on $\gamma_{i}$, say $p^{\prime}$ and $p$ in that order, then
the length of the portion of $\gamma_{i}$ from $s$ to $p$ is $l_{i}$ if and
only if the length of the portion of $\gamma_{i}$ from $s$ to $p^{\prime}$ is
$l_{i}-|L1_{P}(p,p^{\prime})|$.

### Analysis of running time

There are $O(n)$ essential cuts, $O(n)$ Hanan grid points on each cut. Each
tour $\gamma_{i}$ must be no longer than $nD$, where $D$ is the length of the
longest edge of $P$, therefore $l_{i}$ is bounded by $nD$. In total, there are
$O[n\cdot n^{2k}\cdot(nD)^{k}]=O(n^{3k+1}D^{k})$ subproblems. We pre-compute
geodesic L1 shortest paths between Hanan grid points, as well as between Hanan
grid points and essential cuts, which equates to solving the All Pairs
Shortest Path problem in the embedded graph of the Hanan grid. Then, we can
solve each subproblem by iterating through at most $O(n^{2})$ previously
solved subproblems. Thus, the total running time is $O(n^{3k+3}D^{k})$, which
is pseudopolynomial for fixed $k$. This is in congruence with the weak NP-
hardness from Partition, for which there exists a pseudopolynomial (polynomial
in the number of input integers and the largest input integer) time algorithm.
A tighter time bound is $O(n^{2k+3}L^{k})$, where $L$ is the length of a
shortest single orthogonal watchman route of $P$, which is computable in
$O(n)$ time if $P$ is simple and orthogonal [3]. Clearly $L\leq|\partial
P|\leq nD$ and $\max\limits_{i=1,\ldots,k}|\gamma_{i}|\leq L$ (one shortest
single watchman route and $k-1$ routes of length 0 is a feasible solution to
the $k$-WRP). In addition, we need not consider any $L1_{P}(p,p^{\prime})$
whose length is greater than $L$ for recursion (LABEL:eqn:recursion_DP) of the
dynamic programming.

### Fully polynomial-time approximation scheme

To achieve fully polynomial running time for fixed $k$, we bound the number of
subproblems by “bucketing” the lengths of paths in $P$. Let $\\{\gamma_{i}\\}$
be an optimal collection of $k$ routes. Consider that
$L\leq\sum\limits_{i=1,\ldots,k}|\gamma_{i}|$ (the concatenation of
$\\{\gamma_{i}\\}$ can be considered a single watchman route) hence

$\displaystyle\frac{L}{k}\leq\max\limits_{i=1,\ldots,k}|\gamma_{i}|\leq L.$
(2)

Given any $\varepsilon>0$, we divide $L$ into
$\lceil\frac{nk}{\varepsilon}\rceil$ uniform intervals, each no longer than
$\frac{\varepsilon L}{nk}$. The length of any geodesic L1 shortest path we
take into consideration for recursion (LABEL:eqn:recursion_DP) must fall into
one of the intervals, we round it down to the nearest interval endpoint. Then,
apply the dynamic programming algorithm to the new instance with subproblems
defined instead by intervals’ endpoints. Let the solution returned be
$\\{\gamma_{i}^{\prime}\\}$. For clarity, we denote by $d(.)$ distance/length
in the “rounded down” instance. Then

$\displaystyle\max\limits_{i=1,\ldots,k}|\gamma_{i}|\geq\max\limits_{i=1,\ldots,k}d(\gamma_{i})\geq\max\limits_{i=1,\ldots,k}d(\gamma_{i}^{\prime}).$
(3)

The first inequality follows simply from the fact that we round down any
distance from the original instance, the second inequality is by definition,
since $\\{\gamma_{i}^{\prime}\\}$ is an optimal solution of the new instance.
Now, any route in $\\{\gamma_{i}^{\prime}\\}$ must consist of at most $n$
geodesic L1 shortest paths between Hanan grid points on essential cuts, the
length of each differs by no more than $\frac{\varepsilon L}{nk}$ between the
original instance and the “rounded down” instance. Thus, for any $i$

$|\gamma_{i}^{\prime}|-d(\gamma_{i}^{\prime})\leq n\cdot\frac{\varepsilon
L}{nk}$

therefore

$\displaystyle\max\limits_{i=1,\ldots,k}d(\gamma_{i}^{\prime})+\frac{\varepsilon
L}{k}\geq\max\limits_{i=1,\ldots,k}|\gamma_{i}^{\prime}|.$ (4)

Combining all three inequalities (2), (3), (4), we get

$(1+\varepsilon)\max\limits_{i=1,\ldots,k}|\gamma_{i}|\geq\max\limits_{i=1,\ldots,k}|\gamma_{i}^{\prime}|$

with a running time of
$O\left(n^{2k+3}\left(\frac{nk}{\varepsilon}\right)^{k}\right)$.

### Remark

The FPTAS for orthogonal movement (L1 distance) gives a polynomial time
$(\sqrt{2}+\varepsilon)$-approximation to unrestricted movement (L2 distance).

######  Theorem 3.6.

For any fixed $k$, the anchored $k$-WRP in a simple orthogonal polygon has an
FPTAS for the L1 metric and a polynomial-time
$(\sqrt{2}+\varepsilon)$-approximation for the L2 metric.

##  4 Quota $k$-Watchmen in a Simple Polygon

In this section, we assume $P$ is a general simple polygon and the watchmen
can move in any direction within $P$.

### Constant factor polynomial-time approximation

Let $\\{\gamma_{i}\\}$ be an optimal collection of quota $k$-watchman routes
to achieve the visibility area quota of $A$ and let
$OPT=\max\limits_{i=1,\ldots,k}|\gamma_{i}|$. Denote by $C_{g}(r)$ the
geodesic disk of radius $r$ centered at $s$, i.e. the locus of all points
within geodesic distance (length of the geodesic shortest path) of $r$ from
$s$. Let $r=r_{\min}$, where $r_{\min}$ is the smallest value of $r$ such that
$|V(C_{g}(r))|\geq A$; $r_{\min}$ can be computed in $O(n^{2}\log n)$ time
using the “visibility wave” methods in [1]. Clearly,
$r_{\min}\leq\frac{OPT}{2}$, since $C_{g}\left(\frac{OPT}{2}\right)$ encloses
$\\{\gamma_{i}\\}$ and must see an area no smaller than $A$. If we repeatedly
multiply $r$ by 2, at some point we must have
$\frac{r}{2}\leq\frac{OPT}{2}\leq r$, suppose we have reached this point.
Then, $C_{g}(r)$ contains $\\{\gamma_{i}\\}$. Let $\gamma$ be a shortest
single route contained within $C_{g}(r)$ such that $|V(\gamma)|\geq A$ (note
that $\gamma$ is not necessarily the shortest single quota watchman route
overall in $P$).

######  Lemma 4.1.

$\frac{|\gamma|}{k}\leq OPT\leq|\gamma|.$

######  Proof 4.2.

Recall that in Section 3, we proved two similar inequalities for watchman
routes with orthogonal movement seeing the whole polygon. The same holds here
since orthogonality and quota did not play a part in the argument.

We show how to approximate $\gamma$ (it is NP-hard to exactly compute
$\gamma$), and that the number of times we multiply $r$ by 2 is polynomial in
$n$.

######  Lemma 4.3.

[8, Section 3] Given a budget $B\geq 0$ and any $\varepsilon>0$, there exists
an $O\left(\frac{n^{5}}{\varepsilon^{6}}\right)$ algorithm that computes a
route of length at most $(1+\varepsilon)B$ seeing as much area as any route of
length $B$ within $C_{g}(r)$.

We briefly describe the algorithm, and refer the readers to [8] for more
details. First, triangulate $P$, including $s$ as a vertex of the
triangulation. Then, overlay onto the triangulation a regular square grid of
side lengths $\delta=O\left(\frac{\varepsilon B}{n}\right)$ within an axis
aligned square of size $B$-by-$B$ centered at $s$. We consider the set of
(convex) cells that overlap (both fully and partially) with $C_{g}(r)$ and
their vertices, $S_{\delta,r}$. Let $\gamma_{B}$ be the $B$-length route
within $C_{g}(r)$ that achieves the most area of visibility. There exists a
route of length at most $(1+\varepsilon)B$ with vertices coming from
$S_{\delta,r}$ enclosing $\gamma_{B}$, i.e. the boundary of the relative
convex hull (the minimum-perimeter connected superset within $P$, see [8, 9])
of the cells containing vertices of $\gamma_{B}$, thus seeing at least as much
area as $\gamma_{B}$ (Figure 4). If $|\gamma|\leq B\leq\alpha|\gamma|$ for
some $\alpha\geq 1$, using dynamic programming, the algorithm in [8, Section
3] computes a route $\gamma^{\prime}$ of length no longer than
$\alpha(1+\varepsilon)|\gamma|$ with vertices in $S_{\delta,r}$ that sees the
most area, which must be no smaller than $|V(\gamma_{B})|\geq|V(\gamma)|\geq
A$. Using Lemma 4.4, we acquire a polynomial-sized set of values from which we
can search for an appropriate $B$.

Figure 4: Left: $\gamma_{B}$ (red) is a tour no longer than $B$ within
$C_{g}(r)$ (blue) that sees the most area. Right: enclosing $\gamma_{B}$ with
a tour whose vertices are in $S_{\delta,r}$ seeing everything $\gamma_{B}$
sees (green).

######  Lemma 4.4.

$r_{\min}\leq|\gamma|\leq 6nr_{\min}$.

######  Proof 4.5.

The first inequality is straightforward, $r_{min}\leq OPT\leq|\gamma|$.

For the second inequality, first note that if a single watchman travels from
$s$ to $\partial C_{g}(r_{min})$, follows along the whole of $\partial
C_{g}(r_{min})$ then goes back to $s$, he sees an area of $A$, thus $|\partial
C_{g}(r_{min})|+2r_{min}$ is an upper bound on $|\gamma|$. We show that
$|\partial C_{g}(r_{min})|+2r_{\min}\leq 6nr_{min}$. Observe that $\partial
C_{g}(r_{min})$ consists of polygonal chains that are portions of $\partial P$
and circular arcs; the circular arcs have total length no greater than $2\pi
r_{min}$. Each segment in the polygonal part of $\partial C_{g}(r_{min})$ has
length bounded by the sum of geodesic distances from its endpoints to $s$
(triangle inequality), which is no more than $2r_{min}$. There are at most $n$
segments in the polygonal portions of $\partial C_{g}(r_{min})$, therefore
their total length is no greater than $2nr_{\min}$, implying $|\partial
C_{g}(r_{min})|+2r_{min}=2nr_{min}+2\pi r_{min}+2r_{min}\leq 6nr_{min}$.

We divide $6nr_{min}$ into $\lceil\frac{6n}{\varepsilon}\rceil$ uniform
intervals so that each is no longer than $\varepsilon r_{min}$: the smallest
interval endpoint that is no smaller than $|\gamma|$ must also be no larger
than $(1+\varepsilon)|\gamma|$, and hence is the value of $B$ that we desire.
We perform a binary search on the values
$\left\\{0,\frac{6nr_{min}}{\lceil\frac{6n}{\varepsilon}\rceil},\ldots,6nr_{min}\right\\}$
as the input budget for the algorithm in Lemma 4.3, and seek out the smallest
value for which the output route $\gamma^{\prime}$ sees an area no smaller
than $A$. Clearly, $|\gamma^{\prime}|\leq(1+\varepsilon)^{2}|\gamma|$.

Lemma 4.4 also implies that the number of times we double $r$ is polynomially
bounded, in particular, $O(\log n)$, since $r_{min}\leq OPT\leq 6nr_{min}$.

We are now ready to describe the approximation algorithm for the Q$k$-WRP as
follows:

  * •

Step 1: Set $r:=r_{\min}$.

  * •

Step 2: Compute $\gamma^{\prime}$, a $(1+\varepsilon)^{2}$-approximation to
$\gamma$.

  * •

Step 3: Divide $\gamma^{\prime}$ into $k$ subpaths of equal length, each of
which is bounded by $a_{i},a_{i+1}\in\gamma^{\prime}$ ($a_{1}\equiv s\equiv
a_{k+1}$) and denoted by $\gamma^{\prime}_{a_{i}a_{i+1}}$.

  * •

Step 4: For each $i$, we obtain $\gamma_{i}^{\prime}$ by traversing the
geodesic shortest path from $s$ to $a_{i}$, $\gamma^{\prime}_{a_{i}a_{i+1}}$
and the geodesic shortest path from $a_{i+1}$ back to $s$.

  * •

Step 5: Set $r:=2r$, then repeat from Step 2, until $r>6nr_{min}$.

Finally, we return the collection of routes $\\{\gamma_{i}^{\prime}\\}$ that
minimizes $\max\limits_{i=1,\ldots,k}|\gamma_{i}^{\prime}|$ out of all
collections from all values of $r$ in the doubling search.

### Analysis of running time

For each choice of $B$, we execute the
$O\left(\frac{n^{5}}{\varepsilon^{6}}\right)$ algorithm, thus computing an
approximation to $\gamma^{\prime}$ for each value of $r$ takes
$O\left(\frac{n^{5}}{\varepsilon^{6}}\log\left(\frac{n}{\varepsilon}\right)\right)$
time. This step dominates both computing $r_{\min}$ and deriving the
collection $\\{\gamma_{i}^{\prime}\\}$. Since there are $O(\log n)$ iterations
of the doubling search for $r$, the overall running time is
$O\left(\frac{n^{5}}{\varepsilon^{6}}\log\left(\frac{n}{\varepsilon}\right)\log
n\right)$.

######  Theorem 4.6.

The algorithm described above has an approximation factor of $3+\varepsilon$.

######  Proof 4.7.

Since all our choices for $B$ are no larger than $6nr_{\min}$, we can choose
an appropriate $\delta=O\left(\frac{\varepsilon B}{n}\right)$ so that the
geodesic distance from any point on $\gamma^{\prime}$ to $s$ is no longer than
$r+\varepsilon r$. Thus, when $\frac{r}{2}\leq\frac{OPT}{2}\leq r$, any one of
the $k$ routes returned by the algorithm is no longer than
$\frac{|\gamma^{\prime}|}{k}+2r+2\varepsilon
r\leq[(1+\varepsilon)^{2}+2+2\varepsilon]OPT=(3+\varepsilon^{\prime})OPT$,
where $\varepsilon^{\prime}=4\varepsilon+\varepsilon^{2}$. Note that
$\frac{1}{\varepsilon}=\Theta\left(\frac{1}{\varepsilon^{\prime}}\right)$ as
$\varepsilon$ and $\varepsilon^{\prime}$ approach 0, so the running time is in
the same order when written in terms of $\varepsilon^{\prime}$.

### Improving the approximation factor

In the approximation algorithm earlier, we gradually expand $C_{g}(r)$ until
$C_{g}(r)$ contains an optimal $\\{\gamma_{i}\\}$. If in each iteration, we
instead multiply $r$ by a smaller factor, namely $(1+\varepsilon)$, then at
some point $\frac{r}{(1+\varepsilon)}\leq\frac{OPT}{2}\leq r$. The distance
from each point on $\gamma^{\prime}$ to $s$ is then no greater than
$r+\varepsilon r\leq(1+\varepsilon)^{2}\frac{OPT}{2}$. Hence, the length of
any of the $k$ routes returned by the approximation algorithm is bounded by
$\frac{|\gamma^{\prime}|}{k}+(1+\varepsilon)^{2}\frac{OPT}{2}+(1+\varepsilon)^{2}\frac{OPT}{2}\leq(2+\varepsilon^{\prime})OPT$,
where $\varepsilon^{\prime}=4\varepsilon+2\varepsilon^{2}$.

There is however, a trade-off between the approximation factor and the number
of iterations of the multiplicative search for $r$. If we multiply $r$ by
$(1+\varepsilon)$ each time, the search requires $O(\log_{1+\varepsilon}n)$
iterations. Note that

$\log_{1+\varepsilon}n=\log n\frac{\ln 2}{\ln(1+\varepsilon)}=\log
nO\left(\frac{1}{\varepsilon}\right).$

In summary, we can achieve an approximation ratio of
$(2+\varepsilon^{\prime})$ with a running time of
$O\left(\frac{n^{5}}{\varepsilon^{7}}\log\left(\frac{n}{\varepsilon}\right)\log
n\right)=O\left(\frac{n^{5}}{\varepsilon^{\prime
7}}\log\left(\frac{n}{\varepsilon^{\prime}}\right)\log n\right)$ (since
$\frac{1}{\varepsilon}=\Theta\left(\frac{1}{\varepsilon^{\prime}}\right)$).

## References

  * [1] Esther M. Arkin, Alon Efrat, Christian Knauer, Joseph S. B. Mitchell, Valentin Polishchuk, Günter Rote, Lena Schlipf, and Topi Talvitie.  Shortest path to a segment and quickest visibility queries.  Journal of Computational Geometry, 7(2):77–100, 2016.
  * [2] Svante Carlsson, Håkan Jonsson, and Bengt J. Nilsson.  Finding the shortest watchman route in a simple polygon.  Discrete & Computational Geometry, 22:377–402, 1999.
  * [3] Wei-Pang Chin and Simeon Ntafos.  Optimum watchman routes.  In Proceedings of the 2nd Annual Symposium on Computational Geometry, pages 24–33, 1986.
  * [4] Wei-Pang Chin and Simeon Ntafos.  Shortest watchman routes in simple polygons.  Discrete & Computational Geometry, 6(1):9–31, 1991.
  * [5] Moshe Dror, Alon Efrat, Anna Lubiw, and Joseph S. B. Mitchell.  Touring a sequence of polygons.  In Proceedings of the 35th Annual ACM Symposium on Theory of Computing, pages 473–482, 2003.
  * [6] Adrian Dumitrescu and Csaba D. Tóth.  Watchman tours for polygons with holes.  Computational Geometry, 45(7):326–333, 2012.
  * [7] Leonidas Guibas, John Hershberger, Daniel Leven, Micha Sharir, and Robert Tarjan.  Linear time algorithms for visibility and shortest path problems inside simple polygons.  In Proceedings of the 2nd Annual Symposium on Computational Geometry, pages 1–13, 1986.
  * [8] Kien C. Huynh, Joseph S. B. Mitchell, Linh Nguyen, and Valentin Polishchuk.  Optimizing visibility-based search in polygonal domains.  In Proceedings of the 19th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2024), volume 294 of Leibniz International Proceedings in Informatics (LIPIcs), pages 27:1–27:16, 2024.
  * [9] Joseph S. B. Mitchell.  Geometric shortest paths and network optimization.  Handbook of Computational Geometry, 334:633–702, 2000.
  * [10] Joseph S. B. Mitchell and Erik L. Wynters.  Watchman routes for multiple guards.  In Proceedings of the 3rd Canadian Conference on Computational Geometry, pages 126–129, 1991.
  * [11] Bengt J. Nilsson and Eli Packer.  Approximation algorithms for the two-watchman route in a simple polygon.  arXiv preprint arXiv:2309.13428, 2023.
  * [12] Eli Packer.  Computing multiple watchman routes.  In Experimental Algorithms: 7th International Workshop, WEA 2008 Provincetown, MA, USA, May 30-June 1, 2008 Proceedings 7, pages 114–128. Springer, 2008.
  * [13] Csaba D. Tóth, Joseph O’Rourke, and Jacob E. Goodman.  Handbook of Discrete and Computational Geometry.  CRC press, 2017.