Stony Brook University, USA<EMAIL_ADDRESS>Brook University,
USA<EMAIL_ADDRESS>Stony Brook University, USA
<EMAIL_ADDRESS>Linköping University,
<EMAIL_ADDRESS>Authors [100]Theory of computation
$\rightarrow$ Design and analysis of algorithms 2 19th Scandinavian Symposium
on Algorithm Theory (SWAT 2024) SWAT 2024 SWAT 2024 June 12–14, 2024 Helsinki,
Finland

# Optimizing Visibility-based Search in Polygonal Domains

Kien C. Huynh  Joseph S. B. Mitchell  Linh Nguyen111Corresponding author
Valentin Polishchuk

###### Abstract

Given a geometric domain $P$, visibility-based search problems seek routes for
one or more mobile agents (“watchmen”) to move within $P$ in order to be able
to see a portion (or all) of $P$, while optimizing objectives, such as the
length(s) of the route(s), the size (e.g., area or volume) of the portion
seen, the probability of detecting a target distributed within $P$ according
to a prior distribution, etc. The classic watchman route problem seeks a
shortest route for an observer, with omnidirectional vision, to see all of
$P$. In this paper we study bicriteria optimization problems for a single
mobile agent within a polygonal domain $P$ in the plane, with the criteria of
route length and area seen. Specifically, we address the problem of computing
a minimum length route that sees at least a specified area of $P$ (minimum
length, for a given area quota). We also study the problem of computing a
length-constrained route that sees as much area as possible. We provide
hardness results and approximation algorithms. In particular, for a simple
polygon $P$ we provide the first fully polynomial-time approximation scheme
for the problem of computing a shortest route seeing an area quota, as well as
a (slightly more efficient) polynomial dual approximation. We also consider
polygonal domains $P$ (with holes) and the special case of a planar domain
consisting of a union of lines. Our results yield the first approximation
algorithms for computing a time-optimal search route in $P$ to guarantee some
specified probability of detection of a static target within $P$, randomly
distributed in $P$ according to a given prior distribution.

###### keywords:

Quota watchman route problem, budgeted watchman route problem, visibility-
based search, approximation

###### category:

##  1 Introduction

We investigate the Quota Watchman Route problem (QWRP) and the (dual) Budgeted
Watchman Route problem (BWRP) for a single mobile agent (a “watchman”) within
a polygonal domain $P$ in the plane. These problems naturally arise in various
applications, including motion planning, search-and-rescue, surveillance, and
exploration of a polygonal domain, where complete coverage is not feasible due
to shortage of fuel, time, etc. The QWRP seeks a route/tour that sees at least
some specified area of the domain $P$ with a shortest length, while the BWRP
seeks a route/tour that sees the maximum area subject to a length constraint.
Both can be seen as extensions of the well-known Watchman Route Problem (WRP)
with different objectives and constraints.

The challenge in addressing the trade-off between area seen and tour length is
that one is not able to exploit the optimality structure that is implied by
having to see _all_ of a polygon $P$. It is this structure, yielding an
ordered sequence of “essential cuts”, that allows the WRP to be solved
efficiently, e.g., as an instance of the “touring polygons problem” [13].

Results: We address the challenge by establishing new structural results that
enable a careful discretization and analysis, along with carefully crafted
dynamic programs. We provide several new results on optimal visibility search
in a polygon:

(1)

We prove that the QWRP and the BWRP are (weakly) NP-hard, even in a simple
polygon; this is to be contrasted with the WRP, for which exact polynomial-
time algorithms are known in simple polygons.

(2)

For the QWRP in a simple polygon $P$, we give the first fully polynomial-time
approximation scheme (FPTAS), as well as a dual-approximation (with slightly
more efficient running time than the FPTAS) that computes a tour having length
at most $(1+\varepsilon_{1})$ times the length of an optimal tour that sees
area at least $A$ (where $A$ is the area quota), while seeing area at least
$(1-\varepsilon_{2})A$ for any $\varepsilon_{1},\varepsilon_{2}>0$.

(3)

For the BWRP in simple $P$, we compute, in polynomial time, a tour of length
at most $(1+\varepsilon)B$ that sees a region within $P$ of area at least that
seen by an optimal tour of length at most $B$.

(4)

In a multiply connected domain, in a polygon $P$ with holes, we provide
hardness of approximations and a $(1+\varepsilon,O(\log n))$-dual
approximation ($n$ is the number of vertices of $P$) for the BWRP. In the
special case of an arrangement of lines, we obtain polynomial-time exact
algorithms for both problems.

(5)

We solve two visibility-based stochastic search problems that seek to locate a
static target given a prior probability distribution of its location within
$P$: (a) compute the minimum time to achieve a specified detection
probability; (b) compute a search route maximizing the probability of
detection by time $T$ for a mobile searcher.

### Related Work

Chin and Ntafos introduced the classic Watchman Route Problem (WRP) [10]:
compute a shortest closed route (tour) within a polygon $P$ from which every
point of $P$ can be seen; they gave an $O(n)$ time algorithm for computing an
optimal tour in a simple orthogonal polygon, and later results established
polynomial-time exact algorithms for the WRP in a simple polygon $P$, both
with and without an anchor point (depot) [5, 10, 11, 13, 26, 30, 31]. In a
polygon $P$ with holes, the WRP is NP-hard [10, 17] and is, in fact, NP-hard
to approximate better than a logarithmic factor [25]; however, an
$O(\log^{2}n)$-approximation algorithm is known [25]. The BWRP and the QWRP
are natural variants of the WRP.

Another related problem is that of maximum visibility coverage with point
guards: Given an integer $k$, place $k$ point guards within $P$ to maximize
the area of $P$ seen by the guards. When $k$ is arbitrary, the problem is NP-
hard [26], since an exact solution to this problem would yield a method to
compute the minimum number of guards needed to see a polygon. Viewed as a
maximum coverage problem, one can greedily compute an approximation, with
factor $\left(1-\frac{1}{e}\right)$, by iteratively placing a guard that sees
the most unseen area [9, 26].

The BWRP is related to the Orienteering problem. Given a budget constraint and
an edge-weighted graph where each vertex is associated with a prize, the
objective of Orienteering is to find a path/tour within the length budget
maximizing the total reward of the vertices visited. On the other hand, the
QWRP is related to the Quota Traveling Salesperson problem, which aims to
minimize the distance travelled to achieve a given quota of reward. The
Euclidean versions of Orienteering and Quota TSP have polynomial-time
approximation schemes [8, 20, 24]. Both the QWRP and the BWRP can be
considered a reward (the area of $P$ seen by the watchman) collecting process;
however, the main difference lies in the continuous nature of visibility, as
we see portions of the domain as we travel to checkpoints, we must take into
account the area that has been seen previously.

Optimal search theory has been extensively studied in discrete, graph
theoretic settings; see, e.g., [18, 19, 32]. In geometric contexts, searching
and target tracking have been studied in the form of Visibility-based Pursuit-
Evasion games. In [22], the visibility-based version of the pursuit-evasion
game was introduced and formulated as a geometric problem, in which an evader
moves unpredictably, arbitrarily fast within a polygonal domain, and the goal
is to strategically coordinate one or multiple pursuers to guarantee a finite
time of detection. See the survey [12] on visibility-based pursuit-evasion
games.

##  2 The QWRP in a Simple Polygon

###  2.1 Preliminaries and Hardness Results

A simple polygon $P$ is a simply connected subset of $\mathbb{R}^{2}$ whose
boundary, $\partial P$, is a polygonal cycle consisting of a finite set of
line segments, whose endpoints are the _vertices_ ,
$v_{1},v_{2},\ldots,v_{n}$, of $P$. A vertex is reflex (resp. convex) if its
internal angle is at least (resp. at most) 180 degrees. We consider polygons
to be closed sets, including the interior and the boundary. We use the
notation $|\cdot|$ to denote the measure of several types of objects. In the
case of a segment or a route $\gamma$, $|\gamma|$ denotes its length, while
for a polygon $P$, $|P|$ denotes the area of $P$. For a discrete, finite set
$S$, $|S|$ is the cardinality of $S$. Based on the object within the notation,
the interpretation should be apparent.

Point $x\in P$ sees point $y\in P$ if the line segment connecting them lies
entirely within $P$. The visibility polygon of $x$, denoted $V(x)$, is the
closed region of $P$ that $x$ sees; necessarily, $V(x)$ is a simple polygon
within $P$. For a subset $X\subset P$, let $V(X)$ be the set of points that
are seen by at least one point in $X$; formally, $V(X)=\bigcup_{x\in X}V(x)$.
The visibility polygon of a point or a segment can be computed in time $O(n)$
for a simple polygon, or in time $O(n+h\log h)$ for a polygonal domain with
$n$ vertices and $h$ holes [27]. Given a domain $P$ (a simple polygon or a
polygon with holes) and an area quota $0\leq A\leq|P|$, in the QWRP, the
objective is to find a tour (a polygonal cycle) $\gamma$ of minimum length
$|\gamma|$ such that $|V(\gamma)|\geq A$; see Figure 1. Note that when
$A=|P|$, QWRP is the classic Watchman Route Problem.

Figure 1: A route $\gamma$ (red) that sees the white portion of $P$ (the gray
regions are unseen).

We also distinguish between the anchored version (in which $\gamma$ must pass
through a given depot point $s$) and the floating version (in which no depot
is given). We provide the following NP-hardness results (proved in Appendix A)
for both the anchored and floating cases:

######  Theorem 2.1.

The QWRP in a simple polygon is weakly NP-hard, with or without an anchor.

Throughout the paper, we assume a real RAM model of computation [29].

###  2.2 Structural Lemma

Let $\pi_{P}(x,y)$ denote the geodesic shortest path (shortest path
constrained to stay within $P$) between $x\in P$ and $y\in P$; $\pi_{P}(x,y)$
is unique in a simple $P$, and is the segment $xy$ if $x$ sees $y$. For a
subset $S\subseteq P$, the relative/geodesic convex hull of $S$ is the minimal
set that contains $S$ and is closed under taking shortest paths. Equivalently,
the relative convex hull of $S$ is the minimum-perimeter subset of $P$ that
contains $S$. A set is relatively convex if it is equal to its relative convex
hull, and a closed curve is relatively convex if it is the boundary of a
relatively convex set. Let $P_{\gamma}$ denote the connected region bounded by
some closed polygonal chain $\gamma$. If $P_{\gamma}$ is a (sub)polygon of $P$
and $P_{\gamma}$ is relatively convex, then $P_{\gamma}$ is the relative
convex hull of its convex vertices, and all reflex vertices of $P_{\gamma}$
are necessarily reflex vertices of $P$. We similarly define relative convexity
of a polygonal chain $\gamma$: if $\gamma$ is a connected subset of the
boundary of the relative convex hull of $\gamma$, then we say that $\gamma$ is
relatively convex. Geodesic shortest paths and relative convex hulls have been
studied extensively and can be computed efficiently [24].

An optimal solution to the QWRP in a simple polygon $P$ satisfies a structural
lemma:

######  Lemma 2.2.

For a simple polygon $P$ with $n$ vertices, and no depot, an optimal QWRP tour
is a relatively convex simple polygonal cycle of at most $2n$ vertices.

######  Proof 2.3.

Let $\gamma$ be an optimal QWRP tour and let $P^{\prime}=V(\gamma)$ be the
visibility polygon of $\gamma$. Since $\gamma$ is connected, $P^{\prime}$ is a
simple subpolygon of $P$; some edges of $P^{\prime}$ coincide with edges of
$P$ and some are shadow chords (chords separating $V(\gamma)$ from the rest of
$P)$ supported by reflex vertices of $P$. Then $\gamma$ is a shortest watchman
route in the simple polygon $P^{\prime}$. Thus, $\gamma$ is relatively convex
in $P^{\prime}$, and thus in $P$, and $\gamma$ has at most $2n$ vertices,
since $P^{\prime}$ is easily seen to have at most $n$ vertices. (See [11,
25].)

Specifically, the polygon $P^{\prime}=V(\gamma)$ is obtained from $P$ by
removing certain subpolygons (“shadow pockets”) of $P$ that are each defined
by a chord, $vv^{\prime}$, extending from a reflex vertex, $v$, of $P$, along
the line through $v$ and a convex vertex of $\gamma$, to the first point
$v^{\prime}$ on the boundary of $P$. This process introduces a (convex) vertex
$v^{\prime}$ (on an edge of $P$, in general on its interior), and removes at
least one vertex of $P$, on the boundary of the pocket that is cut off by the
chord. Refer to Figure 1. Thus, $P^{\prime}$ has at most $n$ vertices. For a
simple polygon with $n$ vertices, any shortest watchman route has at most $2n$
vertices [5, 10, 11, 13, 26, 30, 31]. Moreover, all reflex vertices of
$P^{\prime}$ must be reflex vertices of $P$, hence all reflex vertices of
$\gamma$ must also be reflex vertices of $P$.

If there is a specified depot $s\in\partial P$, a statement similar to Lemma
2.2 holds. If $s$ is interior to $P$, an optimal tour
$\gamma=(s,w_{1},w_{2},\ldots,w_{k},s)$ through $s$ need not be relatively
convex; however, it is “nearly” relatively convex in that the tour obtained by
replacing the two edges $sw_{1}$ and $w_{k}s$ with the geodesic path
$\pi_{P}(w_{1},w_{k})$ is relatively convex.

###  2.3 Dual approximation algorithm for anchored QWRP

An optimal tour for the QWRP will, in general, have (convex) vertices that are
interior to $P$, at locations within the continuum that are not known to come
from a discrete set. This poses a challenge to algorithms that are to compute
solutions for the QWRP exactly or approximately. We address this challenge by
discretizing an appropriate portion of the domain $P$ using a (Steiner)
triangulation whose faces are small enough that we can afford to round an
optimal tour to vertices of the triangles, while increasing the length of the
tour only slightly, and assuring that the rounded tour continues to see at
least as much of $P$ as the optimal tour did. We focus here on the anchored
case, with a specified depot $s$, which we assume to be on $\partial P$ for
now.

First, we triangulate $P$ (in $O(n)$ time [6]), including $s$ as a vertex of
the triangulation. We then overlay, centered on $s$, a regular square grid of
pixels of side lengths $\delta$ within an axis-aligned square of size
$L$-by-$L$ for a length $L$ that is at least the optimal tour length; we
specify how to determine $\delta$ and $L$ below. The overlay of the grid with
the triangulation yields a partition of $P$ into convex cells of constant
complexity, each of which we triangulate, resulting in an overall Steiner
triangulation of $P$, such that every triangle within distance $L/2$ of $s$
has diameter at most $\delta\sqrt{2}$ and perimeter at most $4\delta$; we let
$S_{\delta,L}$ denote the set of vertices of these triangles. We refer to
$S_{\delta,L}$ as the set of candidate turn points for a route.

######  Lemma 2.4.

For an optimal tour $\gamma$ for the QWRP with area quota $A$, there exists a
polygonal tour $\gamma^{\prime}$ whose vertices are in the set $S_{\delta,L}$
of candidates, such that $\gamma^{\prime}$ is relatively convex,
$|\gamma^{\prime}|\leq|\gamma|+(8+4\sqrt{2})\delta n$ and $V(\gamma)\subseteq
V(\gamma^{\prime})$.

######  Proof 2.5.

Let $c_{1},c_{2},\dots$ be convex vertices of the optimal tour $\gamma$
($\gamma$ is the relative convex hull of such vertices) and let
$\sigma_{1},\sigma_{2},\ldots$ be (closed) cells of the decomposition that
contain the vertices. Let $\gamma^{\prime}$ be the boundary of the relative
convex hull of the cells. By construction, $\gamma^{\prime}$ is a relatively
convex tour enclosing $\gamma$, implying that any point seen by $\gamma$ is
also seen by $\gamma^{\prime}$. Furthermore, since $s\in\partial P$, it
follows that $s$ cannot be in the interior of $P_{\gamma^{\prime}}$, a
subpolygon of $P$, thus $s\in\gamma^{\prime}$.

We claim that $|\gamma^{\prime}|$ is at most $|\gamma|+(8+4\sqrt{2})\delta n$.
For each edge $e^{\prime}$ of $\gamma^{\prime}$ going from $\sigma_{i}$ to
$\sigma_{j}$, we can bound its length by the sum of the length of the edge $e$
of $\gamma$ going from $\sigma_{i}$ to $\sigma_{j}$ ($\gamma^{\prime}$ visits
the cells containing the vertices of $\gamma$ in the same order) and at most
two connections from endpoints of $e$ to vertices of $\sigma_{i},\sigma_{j}$,
which is no more than $2\sqrt{2}\delta$, see Figure 2, right. Additionally,
the part of $\gamma^{\prime}$ along the perimeters of
$\sigma_{1},\sigma_{2},\ldots$ is no longer than $8\delta n$. Hence,
$|\gamma^{\prime}|\leq|\gamma|+(8+4\sqrt{2})\delta n$.

Figure 2: Left: $\gamma^{\prime}$ (blue) is the relative convex hull of the
vertices (blue) of the cells that contain convex vertices of $\gamma$ (red).
Right: Each edge of $\gamma^{\prime}$ that traverses between two different
cells $\sigma_{i},\sigma_{j}$ by triangle inequality, is no longer than the
edge of $\gamma$ between the same cells plus at most two connections to two
vertices of $\sigma_{i},\sigma_{j}$.

From Lemma 2.4, if $\delta=O\left(\frac{\varepsilon|\gamma|}{n}\right)$, then
for approximation purposes within factor $(1+\varepsilon)$, it suffices to
search for a tour whose vertices come from $S_{\delta,L}$. In fact, our
algorithm returns a tour no longer than $(1+\varepsilon_{1})|\gamma|$ for any
$\varepsilon_{1}>0$; however, due to discretization of the area quota, we only
guarantee the tour sees at least $(1-\varepsilon_{2})A$ for any
$\varepsilon_{2}>0$.

We now establish an ordering on the point set $S_{\delta,L}$, so that a
relatively convex chain of the candidate points moves in increasing order.
First, we compute $\mathcal{T}$, the tree of shortest paths rooted at $s$ to
all the candidate points; this takes $O(|S_{\delta,L}|)$ time [21]. The path
from $s$ to a candidate point $s^{\prime}$ in $\mathcal{T}$ is the geodesic
shortest path $\pi_{P}(s,s^{\prime})$. Define a geodesic angular order as
follows: for two candidate points $s_{i},s_{j}$, if $s_{i}$ is to the left of
the extended geodesic shortest path between $s$ and $s_{j}$, i.e
$\pi_{P}(s,s_{j})$ with the last segment extending up to $\partial P$, then
$s_{i}$ precedes $s_{j}$. In case of ties, we break ties by increasing
distance to $s$. For each reflex vertex $r_{i}$ of $P$, we add another
candidate $s_{r_{i}}$ to the list to account for the possibility that $r_{i}$
can appear as two different vertices of a relatively convex polygonal chain;
$s_{r_{i}}$ obeys the aforementioned geodesic angular order but precedes every
candidate point in the subtree of $\mathcal{T}$ rooted at $r_{i}$. Sort the
candidates accordingly, then append $s_{m}:=s_{1}$ to the end of the sorted
list. Any relatively convex chain with vertices sequence oriented clockwise
$(s,s_{i_{1}},s_{i_{2}},\ldots)$ has $1<i_{1}<i_{2}<\ldots$. Without loss of
generality, we consider any relatively convex polygonal chain to be oriented
clockwise.

Next, we examine the optimal substructure of the problem.

######  Lemma 2.6 ([3]).

The visibility region of the geodesic shortest path $\pi_{P}(s,s_{j})$ is the
inclusion-wise minimal set among all visibility regions of all paths from $s$
to $s_{j}$.

Let $C$ be a relatively convex polygonal chain from $s$ to a candidate point
$s_{j}$, and let $s_{i}$ be the vertex of $C$ immediately preceding $s_{j}$.
We identify the overlap of visibility between the segment $s_{i}s_{j}$ and
$C_{s_{i}}$, the sub chain of $C$ from $s$ to $s_{i}$ in Lemma 2.7.

######  Lemma 2.7.

$V(C_{s_{i}})\cap V(s_{i}s_{j})=V(\pi_{P}(s,s_{i}))\cap V(s_{i}s_{j})$.

######  Proof 2.8.

Refer to Figure 3. Let $x\in P$ be a point seen by both $\pi_{P}(s,s_{i})$ and
$s_{i}s_{j}$. Since $x\in V(\pi_{P}(s,s_{i}))$, it follows that $x\in
V(C_{s_{i}})$ (Lemma 2.6). Thus, $x\in V(C_{s_{i}})\cap V(s_{i}s_{j})$ and
$V(\pi_{P}(s,s_{i}))\cap V(s_{i}s_{j})\subseteq V(C_{s_{i}})\cap
V(s_{i}s_{j})$.

On the other hand, let $x\in P$ be seen by both $C_{s_{i}}$ and $s_{i}s_{j}$.
Since $x\in V(C_{s_{i}})\cap V(s_{i}s_{j})$ there exists $x_{1}\in C_{s_{i}}$
and $x_{2}\in s_{i}s_{j}$ such that $xx_{1}$ and $xx_{2}$ are contained within
$P$. Thus, the (pseudo)triangle $xx_{1}x_{2}$ is contained within $P$ since
$P$ has no holes. By our ordering scheme, $s_{j}$ is to the right of
$\pi_{P}(s,s_{i})$ with the last segment extended up to $\partial P$, while
$C_{s_{i}}$ is to the left of it. This implies that in the relatively convex
polygon $P_{C\cup\pi_{P}(s_{,}s_{j})}$, $x_{1},x_{2}$ are in opposite sides
with respect to $\pi_{P}(s,s_{i})$. As we pivot a line of sight around $x$
from $x_{1}$ to $x_{2}$, it must intersect $\pi_{P}(s,s_{i})$ at some point
due to continuity as well as (relative) convexity, therefore
$\pi_{P}(s,s_{i})$ sees $x$. Hence, $V(C_{s_{i}})\cap V(s_{i}s_{j})\subseteq
V(\pi_{P}(s,s_{i}))\cap V(s_{i}s_{j})$.

Figure 3: Proof of Lemma 2.7.

Based on Lemma 2.7, the overlap of visibility between the segment
$s_{i}s_{j}$, for $i<j$, and any relatively convex chain $C_{s_{i}}$ from $s$
to $s_{i}$ does not depend on the vertices between $s$ and $s_{i}$. This leads
to the optimal substructure utilized by our dynamic programming algorithm.

######  Lemma 2.9.

$C$ is a shortest relatively convex polygonal chain from $s$ to $s_{j}$ that
sees at least some area $\overline{A}$ if and only if $C_{s_{i}}$ is a
shortest relatively convex polygonal chain from $s$ to $s_{i}$ that sees at
least area $\overline{A}-|V(s_{i}s_{j})\setminus V(\pi_{P}(s,s_{i}))|$.

######  Proof 2.10.

We write $V(C)$ as the union of 2 disjoint sets $V(C_{s_{i}})$ and
$V(s_{i}s_{j})\setminus V(C_{s_{i}})$. Notice that

$\displaystyle V(s_{i}s_{j})\setminus
V(C_{s_{i}})=V(s_{i}s_{j})\setminus(V(C_{s_{i}})\cap
V(s_{i}s_{j}))=V(s_{i}s_{j})\setminus(V(\pi_{P}(s,s_{i}))\cap V(s_{i}s_{j}))$
$\displaystyle=V(s_{i}s_{j})\setminus V(\pi_{P}(s,s_{i}))$

therefore $|V(C_{s_{i}})|\geq\overline{A}-|V(s_{i}s_{j})\setminus
V(\pi_{P}(s,s_{i}))|.$ As a result, $C_{s_{i}}$ must be the shortest chain to
achieve a visibility area of $\overline{A}-|V(s_{i}s_{j})\setminus
V(\pi_{P}(s,s_{i}))$, since the existence of a shorter chain contradicts the
optimality of $C$, and vice versa.

A subproblem in the dynamic program is determined by a candidate point $s_{j}$
and an area quota $\overline{A}$. Let $\pi(s_{j},\overline{A})$ denote the
length of a shortest relatively convex polygonal chain from $s$ to $s_{j}$
that can see area at least $\overline{A}$; and let $C(s_{j},\overline{A})$
denote the associated optimal chain. Initialize $\pi(s,|V(s)|)=0$. The Bellman
recursion for each subproblem with $j=1,2,\ldots,m$ and all values of
$\overline{A}$ would be given as follows, for all $i<j$ such that $s_{j}$ sees
$s_{i}$ and $C(s_{i},\overline{A}-|V(s_{i}s_{j})\setminus
V(\pi_{P}(s,s_{i}))|)\cup s_{i}s_{j}$ is relatively convex

$\displaystyle\begin{split}\pi(s_{j},\overline{A})&=\min\limits_{i}\left\\{\pi(s_{i},\overline{A}-|V(s_{i}s_{j})\setminus
V(\pi_{P}(s,s_{i}))|)+|s_{i}s_{j}|\right\\},\\\
C(s_{j},\overline{A})&=C(s_{i},\overline{A}-|V(s_{i}s_{j})\setminus
V(\pi_{P}(s,s_{i}))|)\cup s_{i}s_{j}.\end{split}$

Then, return $C(s_{m},A)$. Correctness of the algorithm follows from the
principle of optimality.

Figure 4: Solving subproblem $(s_{j},\overline{A})$.

Note that there always exists an optimal solution $i$ to the above recursion
such that $C(s_{i},\leavevmode\nobreak\ \overline{A}\leavevmode\nobreak\
-\leavevmode\nobreak\ |V(s_{i}s_{j})\setminus\leavevmode\nobreak\
V(\pi_{P}(s,s_{i}))|)\cup\leavevmode\nobreak\ s_{i}s_{j}$ is relatively
convex. Otherwise, we can shortcut $C(s_{i},\leavevmode\nobreak\
\overline{A}\leavevmode\nobreak\ -\leavevmode\nobreak\
|V(s_{i}s_{j})\setminus\leavevmode\nobreak\
V(\pi_{P}(s,s_{i}))|)\cup\leavevmode\nobreak\ s_{i}s_{j}$ by connecting
$s_{j}$ to the closest reflex vertex (of $P$) or the point of tangency in
$C(s_{i},\overline{A}-|V(s_{i}s_{j})\setminus V(\pi_{P}(s,s_{i}))|)$.

Since $\overline{A}$ can take values from a continuous set, it is impractical
to tabulate all such values. Instead, we bucket $A$ into uniform intervals,
and let the subproblems be defined by interval endpoints. We round down the
area of any visibility polygon to the nearest interval. Since we sum up the
area of at most $2(n-3)+\frac{2L}{\delta}$ visibility polygons (each of the
$n-3$ diagonals in the triangulation of $P$ and $\frac{L}{\delta}$
horizontal/vertical grid lines potentially has at most 2 vertices of the tour
returned by the dynamic programming algorithm since we enforce relative
convexity), if we denote by $I$ the length of each interval, the area lost by
rounding down is at most $I\left(2(n-3)+\frac{2L}{\delta}\right)$. We run the
algorithm on the “rounded down” instance with area quota
$A\leavevmode\nobreak\ -\leavevmode\nobreak\
I\left(2(n-3)+\frac{2L}{\delta}\right)$, and since the optimal solution of the
original instance is a feasible solution of the new instance, the algorithm
returns a tour no longer than an optimal tour $\gamma^{\prime}$ (that sees at
least area $A$).

It remains to compute an appropriate $L$ such that an optimal tour $\gamma$ is
contained within the bounding box of the grid. Denote by $C_{g}(r)$ the
perimeter of the geodesic disk of radius $r$ centered at $s$ (the locus of
points whose length of the geodesic path to $s$ is no greater than $r$). Let
$r:=r_{min}$ where $r_{min}$ is the smallest value of $r$ such that
$|V(C_{g}(r))|=A$; then, $r_{min}$ is a lower bound on $|\gamma|$, since a
tour of length $r_{min}$ has geodesic radius at most $r_{min}/2$ and thus
cannot see an area of $A$. We can compute $r_{min}$ by the “visibility wave”
methods in [1] by considering all $O(n^{2})$ edges of the visibility graph
$G_{v}$ of $P$ (nodes are vertices of $P$ and two nodes are adjacent if they
are visible to one another); we have a sequence of visibility edges hit by
$C_{g}(r)$ for the first time in the process of increasing $r$, obtained by
sorting the distance from every visibility edge to $s$ in $O(n^{2}\log n)$
time.

Moreover, $|C_{g}(r)|+2r$ is an upper bound on $|\gamma|$, since if the
watchman goes from $s$ to $C_{g}(r)$ ($s$ may not be on $C_{g}(r)$), follows
along the whole perimeter $C_{g}(r)$ then goes back to $s$, he sees an area
$A$. We argue that $|C_{g}(r)|=O(nr)$ (which implies $|\gamma|\leq
O(nr)+2r=O(nr)$) as follows: $C_{g}(r)$ consists of polygonal chains that are
portions of $\partial P$ and circular arcs; the circular arcs have total
length $O(r)$. For each segment in the polygonal part of $C_{g}(r)$, we can
bound its length by the sum of geodesic distances from its endpoints to $s$
(triangle inequality), which is no more than $2r$. There are at most $O(n)$
segments in the polygonal portions of $C_{g}(r)$, therefore their total length
is $O(nr)$, implying $|C_{g}(r)|=O(nr)+O(r)=O(nr)$.

We initialize $L:=r$ and run the dynamic program with the following $\delta$
and $I$

$\displaystyle\delta=\frac{\varepsilon_{1}L}{16+8\sqrt{2}n},\qquad
I=\frac{\varepsilon_{1}\varepsilon_{2}A}{2(n-3)\varepsilon_{1}+(32+16\sqrt{2})n}.$

If $|\gamma|\leq L\leq 2|\gamma|$, the approximate tour $\gamma^{\prime}$
returned by the dynamic program will be such that
$V|\gamma^{\prime}|\geq(1-\varepsilon_{2})|V(\gamma)|$ and
$|\gamma^{\prime}|\leq(1+\varepsilon_{1})|\gamma|$. Else, set $L:=2L$. The
number of iterations of the doubling search is clearly $O(\log n)$. The
resulting theorem (proof details in Appendix B):

######  Theorem 2.11.

Given a starting point $s$, a dual approximation $\gamma^{\prime}$ to an
optimal solution $\gamma$ of the QWRP, with area quota $A$, in a simple
polygon with $n$ vertices, satisfying
$|V(\gamma^{\prime})|\geq(1-\varepsilon_{2})A$ and
$|\gamma^{\prime}|\leq(1+\varepsilon_{1})|\gamma|$ for any
$\varepsilon_{1},\varepsilon_{2}>0$, can be computed in
$O\left(\frac{n^{5}}{\varepsilon_{1}^{5}\varepsilon_{2}}\log n\right)$ time if
$s\in\partial P$ or
$O\left(\frac{n^{9}}{\varepsilon_{1}^{9}\varepsilon_{2}}\log n\right)$ time if
$s\notin\partial P$.

##  3 The BWRP in a Simple Polygon

######  Theorem 3.1.

[proof in Appendix A] The BWRP in a simple polygon is weakly NP-hard.

###  3.1 Approximation algorithm for anchored BWRP

For a given budget length $B>0$, and any fixed $\varepsilon>0$, we compute a
route of length at most $(1+\varepsilon)B$ that sees at least as much area as
an area-maximizing route of length $B$.

######  Claim 1.

Without loss of generality, we can assume that $B$ is less than the length of
an optimal watchman route for $P$; otherwise, the solution is simply an
optimal WRP tour. Hence, an optimal budgeted watchman route $\gamma$ is
necessarily the shortest watchman route of the subpolygon $V(\gamma)$, and so
$\gamma$ is relatively convex (otherwise, we can shortcut $\gamma$ and expand
the remaining length budget to see more area, contradicting the optimality of
$\gamma$).

Since it suffices to consider only relatively convex routes for the BWRP, the
observation in Lemma 2.7 allows us to prove the structure of an optimal BWRP
tour.

######  Lemma 3.2.

$C$ is a relatively convex polygonal chain from $s$ to $s_{j}$ of length at
most $\overline{B}$ that sees the largest area possible if and only if
$C_{s_{i}}$ is a relatively convex polygonal chain from $s$ to $s_{i}$ of
length at most $\overline{B}-|s_{i}s_{j}|$ that sees the largest area
possible.

######  Proof 3.3.

The proof is identical to that of Lemma 2.9 and hence omitted in this version.

We decompose $P$ by overlaying a triangulation and regular square grid of
$\delta$-sized pixels within an axis-aligned square of size $B$-by-$B$,
centered on $s$, then sort the set of candidates $S_{\delta,B}$ according to
the geodesic angular order defined for the QWRP. Similarly, there exists a
route $\gamma^{\prime}$ of length at most $\gamma+(8+4\sqrt{2})\delta n$ with
vertices in $S_{\delta,B}$.

Let $a(s_{j},\overline{B})$ be the optimal area that a relatively convex
polygonal chain from $s$ to $s_{j}$ that is no longer than $\overline{B}$ can
see; and let $C(s_{j},\overline{B})$ be the associated optimal chain of the
subproblem $(s_{j},\overline{B})$. Initialize $a(s,0)=|V(s)|$. The Bellman
recursion for each subproblem with $j=1,2,\ldots,m$ and all values of
$\overline{B}$ would be given as follows, for all $i<j$ such that $s_{j}$ sees
$s_{i}$ and $C(s_{i},\overline{B}-|s_{i}s_{j}|)\cup s_{i}s_{j}$ is relatively
convex

$\displaystyle\begin{split}a(s_{j},\overline{B})&=\max\limits_{i}\left\\{a(s_{i},\overline{B}-|s_{i}s_{j}|)+|V(s_{i}s_{j})\setminus
V(\pi_{P}(s,s_{i}))|\right\\},\\\
C(s_{j},\overline{B})&=C(s_{i},\overline{B}-|s_{i}s_{j}|)\cup
s_{i}s_{j}.\end{split}$

Then, return $\gamma^{\prime}:=C(s_{m},B+(8+4\sqrt{2})\delta n)$.

To bound the number of subproblems, we consider a partition of an interval of
length $B+(8+4\sqrt{2})\delta n$ into uniform intervals, and round up the
length of any segment $s_{i}s_{j}$ to the nearest interval endpoint. Let $I$
be the length of each interval, we run the algorithm on a new instance with
budget $B+(8+4\sqrt{2})\delta n+\left(2(n-3)+\frac{2B}{\delta}\right)I$ and
the subproblems defined by intervals’ endpoints. The optimal solution of the
original instance is a feasible solution of the new instance; thus, we find a
route seeing as much as the optimal route of the original instance. The values
of $\delta$ and $I$ can be set as follows

$\displaystyle\delta=\frac{\varepsilon B}{(16+8\sqrt{2})n},\qquad
I=\frac{\varepsilon^{2}B}{4(n-3)\varepsilon+(64+32\sqrt{2})n,}$

so that $B+(8+4\sqrt{2})\delta
n+\left(2(n-3)+\frac{2B}{\delta}\right)I\leq(1+\varepsilon)B$. In Appendix B
we prove:

######  Theorem 3.4.

Given a starting point $s$, a route of length at most $(1+\varepsilon)B$
seeing at least as much area as is seen by an optimal route of length $B$ for
the BWRP in a simple polygon with $n$ vertices can be computed in
$O\left(\frac{n^{5}}{\varepsilon^{6}}\right)$ time if $s\in\partial P$ or
$O\left(\frac{n^{9}}{\varepsilon^{10}}\right)$ time if $s\notin\partial P$.

###  3.2 From anchored BWRP to an FPTAS for anchored QWRP

We can adapt the algorithm for the anchored BWRP above to obtain an FPTAS for
the anchored QWRP. Let $\gamma$ be an optimal QWRP tour, suppose we have some
$L$ such that $|\gamma|\leq L\leq 2|\gamma|$. We divide $L$ into
$\displaystyle\frac{L}{\lceil\frac{2}{\varepsilon}\rceil}$ uniform intervals,
each of length no greater than $\varepsilon|\gamma|$. The smallest interval
endpoint $L^{\prime}$ that is no smaller than $|\gamma|$, is a
$(1+\varepsilon)$-approximation to $|\gamma|$. We can iterate through interval
endpoints as the budget constraint and use the approximation algorithm for the
BWRP to compute a route of length at most $(1+\varepsilon)L^{\prime}$ that
sees as much as an area-maximizing route of length $L^{\prime}$ does, which
sees more area than does $\gamma$. The result is the following theorem, which,
in contrast with the earlier Theorem 2.11, is not a dual approximation
(allowing for a relaxation of the quota constraint), but an FPTAS for
optimizing the length, subject to a hard constraint on the area seen. The
running time of the algorithm in the dual approximation of Theorem 2.11,
however, is better than that of the FPTAS, so it may be preferred in some
settings.

######  Theorem 3.5.

[proof in Appendix B] Given a starting point $s$, an approximation
$\gamma^{\prime}$ to an optimal solution $\gamma$ of the QWRP, with area quota
$A$, in a simple polygon with $n$ vertices, satisfying
$|V(\gamma^{\prime})|\geq A$ and
$|\gamma^{\prime}|\leq(1+\varepsilon)|\gamma|$ for any $\varepsilon>0$, can be
computed in $O\left(\frac{n^{5}}{\varepsilon^{6}}\log
n\log\frac{1}{\varepsilon}\right)$ if $s\in\partial P$ or
$O\left(\frac{n^{9}}{\varepsilon^{10}}\log n\log\frac{1}{\varepsilon}\right)$
if $s\notin\partial P$.

##  4 Floating QWRP and BWRP

When the starting point $s$ of the tour is not specified (the so called
“floating” case), the WRP tends to be trickier: known algorithms for the
floating WRP are $O(n)$-factor slower than in the non-floating case [10, 5,
11, 31, 13, 26, 30]. If the optimal tour is not convex (but only relatively
convex), one can iterate through all reflex vertices of $P$ as choices for
$s$, and thus reduce the floating version to the basic WRP; the same can be
done for QWRP and BWRP. Thus, the remaining challenge is to find the shortest
(strictly, not just relatively) convex tour.

Figure 5: What is seen from the interior of a segment does not change as the
segment is moved locally: whatever was hidden, but becomes seen from an
interior point (red), was seen by a neighboring point (black) before the move.

Any convex polygon can be outer-approximated by a convex polygon with a
constant number of vertices: Dudley’s approximation [2, 14, 23] implies that
for any length-$L$ tour $\gamma$, there is a length-$(1+\varepsilon)L$ tour
$\gamma^{\prime}$ with $O\left(\frac{1}{\sqrt{\varepsilon}}\right)$ vertices
that sees at least as much area as $\gamma$ does. To find $\gamma^{\prime}$
(either for QWRP or BWRP), we use the techniques from [26]: For each of the
$O(n^{4})$ cells of the visibility decomposition $D$ (the visibility graph
$G_{v}$ of $P$ as defined Section 2.3, with maximally extended edges), points
within the cell have visibility polygons that are combinatorially equivalent,
implying that the area seen by any point in the cell is given by the same
formula. Moreover, if each vertex of a tour sits within a fixed cell of $D$
and each edge of the tour passes through the same set of cells, the total area
seen from the tour is given by the same formula: the interiors of the edges do
not add to the area seen, so the total seen area is a function,
$f(v_{1},\dots,v_{k})$, of only the positions $v_{i}$ of the tour’s
$k=O\left(\frac{1}{\sqrt{\varepsilon}}\right)$ vertices (Fig. 5). We further
decompose the cells of $D$ by lines through all of $D$’s vertices. If the
vertices of the tour are in the same cells of this refined $O(n^{8})$-complex
decomposition $D^{\prime}$, then the edges of the tour pass through the same
cells of $D$. We iterate through all $O(n^{8k})$ placements of vertices of the
tour into cells of $D^{\prime}$. For each placement, finding $\vec{v}$
maximizing the seen area, $f(\vec{v})$, amounts to solving an $O(k)$-sized
system of polynomial equations having $O(k)$ algebraic degree (the Lagrangian
of the problem will contain the constraint that the tour’s length is $L$,
consisting of $k$ terms and will have to be squared $O(k)$ times before
becoming a polynomial). The solution can be found in $k^{O(k)}$ time [4,
Section 3.4]. We summarize in the following theorems:

######  Theorem 4.1.

Let $\gamma$ be an optimal QWRP (no starting point) tour. In
$n^{O\left(\frac{1}{\sqrt{\varepsilon}}\right)}$ time, a tour of length at
most $(1+\varepsilon)|\gamma|$ can be found that sees at least as much area as
does $\gamma$.

######  Theorem 4.2.

In $n^{O\left(\frac{1}{\sqrt{\varepsilon}}\right)}$ time, a BWRP (no starting
point) tour of length $(1+\varepsilon)L$ can be found that sees at least as
much area as does any tour of length $L$.

##  5 Domains that are a Union of Lines

We consider the QWRP and the BWRP in a domain $P$ that is a connected union
(arrangement) of lines; it suffices to truncate the lines within a bounding
box that encloses all vertices of the line arrangement, so that $P$ is
bounded. Such domains, which are a special case of polygons with holes, have
been studied in the context of the watchman route problem [15, 16]. In this
setting, the QWRP seeks to minimize the length of a route contained within $P$
that visits at least a specified number of (truncated) lines, and the BWRP
seeks to maximize the number of lines visited by a route within $P$ of length
at most some budget. In this section we do not assume a depot $s$ is
specified.

For a set of lines $\mathcal{L}$, let $\mathcal{A}(\mathcal{L})$ denote the
arrangement formed by $\mathcal{L}$. We assume that not all of the lines are
parallel so that the union is connected. All of a line can be seen from any
point incident on it. Let $G(\mathcal{L})$ denote the weighted planar graph
with vertex $V(\mathcal{A}(\mathcal{L}))$ of intersections between lines. Two
vertices in the graph are connected by an edge with Euclidean weight if they
share the same edge in $\mathcal{L}$. Since the watchman is constrained to
travel within $\mathcal{A}(\mathcal{L})$ and the only time the route can have
turning points not in $V(\mathcal{A}(\mathcal{L}))$ is when it traces out the
same edge of $G(\mathcal{L})$ consecutively in opposite directions, turning
somewhere interior to that edge. However, then we can shortcut that portion of
the route altogether while maintaining visibility coverage, it is easy to see
that any optimal route for BWRP or QWRP is polygonal and its vertices is a
subset of $V(\mathcal{A}(\mathcal{L}))$.

We first explain our results for the QWRP, then we use them to solve the BWRP.
The following observation is essential to our algorithm: a line intersects a
tour $\gamma$ if and only if it intersects the convex hull of $\gamma$. We
define the _quota intersecting convex hull_ problem as follows: compute a
cyclic sequence $(v_{1},v_{2},\ldots,v_{h})$ of vertices $v_{i}\in
V(\mathcal{A}(\mathcal{L}))$ in convex position such that the number of lines
intersecting the convex polygon $(v_{1},v_{2},\ldots,v_{h})$ is at least some
specified $Q>0$ and $\sum_{i}^{h}|\pi(v_{i},v_{i+1})|$ is minimized
$(v_{h+1}=v_{1})$, where $\pi(s,t)=\pi_{G}(s,t)$ is the shortest path
connecting $s$ and $t$ in $G(\mathcal{L})$. We show the relationship between
the quota intersecting convex hull problem and the QWRP in an arrangement of
lines.

######  Lemma 5.1.

An optimal solution to the quota intersecting convex hull problem yields an
optimal solution to the QWRP in an arrangement of lines.

######  Proof 5.2.

Suppose $(v_{1},v_{2},\ldots,v_{h})$ is an optimal solution to the quota
intersecting convex hull problem of length $L$ intersecting $Q$ lines. We
concatenate $\pi(v_{1},v_{2}),\ldots,\pi(v_{h-1},v_{h})$ and
$\pi(v_{h},v_{1})$ to form $\gamma$. Every line intersecting the convex
polygon $(v_{1},v_{2},\ldots,v_{h})$ must intersect $\gamma$ as well. Thus,
$\gamma$ is a route of length $\sum_{i}^{h}|\pi(v_{i},v_{i+1})|=L$ seeing $Q$
lines.

We claim that there is no solution $\gamma^{\prime}$ to the QWRP intersecting
$Q$ lines that is strictly shorter than $\gamma$. Suppose to the contrary,
take the convex hull of $\gamma^{\prime}$, which has vertices in
$V(\mathcal{A}(\mathcal{L}))$ since vertices of $\gamma^{\prime}$ are in
$V(\mathcal{A}(\mathcal{L}))$. The vertices of the convex hull of
$\gamma^{\prime}$ form a cyclic sequence that is feasible for the quota
intersecting convex hull problem, and the length is exactly
$|\gamma^{\prime}|$ (or $\gamma^{\prime}$ could be shortened while still
intersecting $Q$ lines), which is strictly smaller than $L$. Thus,
$\gamma^{\prime}$ yields a feasible cyclic sequence intersecting $Q$ lines
while the length is shorter than $\gamma$, violating the assumption that
$(v_{1},v_{2},\ldots,v_{h})$ is optimal.

Note that there can be many optimal solutions to the quota intersecting convex
hull problem yielding the same tour (Figure 6).

Figure 6: Multiple optimal solutions to the quota intersecting convex hull
problem corresponding to the same optimal solution of the QWRP.

We give a dynamic programming algorithm to solve the quota intersecting convex
hull problem. Fix one vertex to be the lowest vertex, let that vertex be
$v_{1}$. We will examine all possible choices of $v_{1}$, and find the optimal
cyclic sequence with each choice. Let $\\{v_{2},v_{3},\ldots,v_{m-1}\\}$ be
the list of vertices above $v_{1}$ sorted by increasing angle with the left
horizontal ray passing through $v_{1}$, breaking ties by increasing distance
to $v_{1}$. Then, set a new element $v_{m}:=v_{1}$ and append it to the list.
Thus, an optimal cyclic sequence $(v_{1},v_{i_{2}},v_{i_{3}},\ldots,v_{m})$
has $1<i_{2}<i_{3}<\ldots<m$. We can restrict ourselves to ordered pairs
$(v_{i},v_{j})$ of consecutive vertices where $1\leq i<j\leq m$ and either
$i\neq 1$ or $j\neq m$ in the sequence.

For $1\leq i<j\leq m$ and either $i\neq 1$ or $j\neq m$, denote by
$\mathcal{L}_{i,j}$ the lines that intersect the segment $v_{i}v_{j}$
(including at the endpoints $v_{i},v_{j}$). Each vertex $v_{j}$ and a quota
value $\overline{Q}$ define a subproblem. Let $\pi(v_{j},\overline{Q})$ be the
shortest length of a sequence of vertices in convex position from
$(v_{1},\ldots,v_{j})$ intersecting at least $\overline{Q}$ lines. Starting
from $v_{1}$, we initialize $\pi(v_{1},|\mathcal{L}_{1,1}|)=0$ with the
associated sequence $(v_{1})$. For $j=2,\ldots,m$ and
$\overline{Q}=1,2,\ldots,n$, we solve the subproblems $(v_{j},\overline{Q})$
by the following Bellman recursion, for all $i<j$ such that the sequence
associated with
$(v_{i},\overline{Q}-|\mathcal{L}_{i,j}\setminus\mathcal{L}_{1,i}|)$ and
$v_{j}$ are in convex position (Figure 7)

$\pi(v_{j},\overline{Q})=\min\limits_{i}\left\\{\pi(v_{i},\overline{Q}-|\mathcal{L}_{i,j}\setminus\mathcal{L}_{1,i}|)+|\pi(v_{i},v_{j})|\right\\}.$

Figure 7: Solving subproblem $(v_{j},\overline{Q})$. The sequence of vertices
in convex position is drawn on the left with a dashed red chain, and the
corresponding part of $\gamma$ is drawn with solid red segments on the right.

Correctness of the algorithm follows from these two claims:

  * •

Given a sequence of vertices in convex position $(v_{1},\ldots,v_{i},v_{j})$,
any line intersecting both $\pi(v_{i},v_{j})$ and the subsequence from $v_{1}$
to $v_{i}$, $(v_{1},\ldots,v_{i})$ must intersect the segment $v_{1}v_{i}$ and
vice versa due to continuity and convexity. If a sequence
$(v_{1},\ldots,v_{i},v_{j})$ is the shortest among all sequences from $v_{1}$
to $v_{j}$ intersecting at least $\overline{Q}$ lines, then the subsequence
from $v_{1}$ to $v_{i}$ is the shortest sequence from $v_{1}$ to $v_{i}$
intersecting $\overline{Q}-|\mathcal{L}_{i,j}\setminus\mathcal{L}_{1,i}|$.

  * •

The sequence $(v_{1},\ldots,v_{i})$ associated with optimal solution $i$ to
the Bellman recursion is such that $(v_{1},\ldots,v_{i})\cup(v_{j})$ are in
convex position.

######  Theorem 5.3.

[proof in Appendix B] The QWRP and the BWRP in an arrangement of lines can be
solved in $O(n^{7})$ time.

######  Remark 5.4.

When $Q=n$, the algorithm solves the classic WRP in an arrangement of lines,
thus our result improves upon the $O(n^{8})$ solution in [16].

##  6 The QWRP and BWRP in a Polygon With Holes

###  6.1 Hardness of approximation

We state the following Theorems and defer their proofs to Appendix A:

######  Theorem 6.1.

The QWRP in a polygon with holes cannot be approximated, in polynomial time,
within a factor of $c\log n$ for some constant $c>0$, unless P = NP.

######  Theorem 6.2.

The BWRP in a polygon with holes cannot be approximated, in polynomial time,
within a factor of $\left(1-\varepsilon\right)$ for arbitrary $\varepsilon>0$,
unless P = NP.

###  6.2 Approximation algorithm for the BWRP in a polygon with holes

We decompose $P$ into small convex cells and obtain the set of candidates
$S_{\delta,B}$ as in the case with the BWRP in a simple polygon.

######  Theorem 6.3.

There exists a route $\gamma^{\prime}$ whose vertices are a subset of
$S_{\delta,B}$ such that $V(\gamma)\subseteq V(\gamma^{\prime})$ and
$|\gamma^{\prime}|\leq(1+\varepsilon)B$.

######  Proof 6.4.

Consider an edge $e$ of $\gamma$ whose endpoints lie in cells $\sigma_{i}$ and
$\sigma_{j}$. We append $\partial\sigma_{i}$ and $\partial\sigma_{j}$ to
$\gamma$. If the endpoints of $e$ are not vertices of $\sigma_{i}$ and
$\sigma_{j}$, we replace $e$ with a set of edges whose endpoints are candidate
points. The procedure can be described with a physical analog: we slide an
elastic string between the two intersection points of $e$ with $\sigma_{i}$
and $\sigma_{j}$ towards the exterior of $\gamma$ until the two endpoints
coincide with vertices of $\sigma_{i}$ and $\sigma_{j}$, the string is pulled
taut and never passes through a hole; see Figure 8. The result is a geodesic
path $e^{\prime}$ between two vertices of $\sigma_{i}$ and $\sigma_{j}$ that
is no longer than $|e|+2\sqrt{2}\delta$.

Repeating the process for every edge of $\gamma$, we obtain $\gamma^{\prime}$.
If a point $x$ seen by $\gamma$ is inside of $P_{\gamma^{\prime}}$, the
extended line of vision between $x$ and $\gamma$ must intersect with
$\gamma^{\prime}$ since there is no hole between $\gamma$ and
$\gamma^{\prime}$. If $x$ is outside of $P_{\gamma^{\prime}}$, then the line
of vision between $x$ and $\gamma$ must intersect $\gamma^{\prime}$ due to the
Jordan Curve Theorem. Thus, $\gamma^{\prime}$ sees everything that $\gamma$
sees, moreover $\gamma^{\prime}$ passes through $s$, a vertex in the
decomposition. Since $\gamma$ has $O(n^{2})$ vertices [25], for an appropriate
choice of $\delta=O\left(\frac{\varepsilon B}{n^{2}}\right)$ we have
$|\gamma^{\prime}|\leq(1+\varepsilon)B$.

Figure 8: Replacing each edge (red) with the perimeters of the two cells
containing its endpoints and a geodesic path of the same homotopy type (blue).

We apply a known result for the Submodular Orienteering problem [7]: Given a
weighted directed graph $G$, two nodes $s$ and $t$ (which need not be
distinct), a budget $B>0$, and a monotone submodular reward function defined
on the nodes, find an $s$-$t$ walk that maximizes the reward, under the
constraint that the length of the walk is no greater than $B$.

Let $G_{1}$ be the visibility graph on the candidates set with Euclidean edge
weights. Let $G_{2}$ be the line graph of $G_{1}$: nodes of $G_{2}$ correspond
to edges of $G_{1}$, and two nodes in $G_{2}$ are adjacent if their respective
edges in $G_{1}$ are incident. The weight of an edge of $G_{2}$ is the sum of
the two edges in $G_{1}$ corresponding to its endpoints, divided by two, thus
a closed walk of length $B$ in $G_{1}$ corresponds to a closed walk of length
$B$ in $G_{2}$ and vice versa. We apply the approximation algorithm from [7]
on $G_{2}$ to compute a closed walk from any node in $G_{2}$ corresponding to
an edge incident with $s$, with the area of visibility as the reward function
and budget $(1+\varepsilon)B$. The reason for using the line graph $G_{2}$ is
that, in the Submodular Orienteering problem, rewards are associated with
nodes, while in the context of the BWRP, rewards are accumulated when
traversing edges of the visibility graph $G_{1}$. We obtain the following:

######  Theorem 6.5.

Given a polygon $P$ with holes with $n$ vertices, let $\beta\geq 2$ be any
constant of choice and $OPT$ be the maximum area that a route $\gamma$ of
length $B$ can see. The BWRP has a dual approximation algorithm that computes
a tour of length at most $(1+\varepsilon)B$ that sees area at least
$\Omega\left(\frac{OPT\log\beta}{\log n}\right)$, with running time
$\left(\frac{n}{\varepsilon}\log
B\right)^{O\left(\beta\log\frac{n}{\varepsilon}/\log\beta\right)}$.

######  Proof 6.6.

Let $k$ be the number of edges in the walk $\gamma^{\prime}$ returned by the
recursive greedy algorithm in [7]. Then
$|V(\gamma^{\prime})|=\Omega\left(\frac{OPT\log\beta}{\lceil 1+\log
k\rceil}\right)$. Since $G_{2}$ has $O(n^{4})$ nodes, it follows that
$k=O(n^{4})$ and $|V(\gamma^{\prime})|=\Omega\left(\frac{OPT\log\beta}{\log
n}\right)$.

##  7 Optimal Visibility-based Search for a Randomly Distributed Target

Our results can be applied to solve two problems of searching a randomly
distributed static target in a simple polygon $P$: Given a prior distribution
of the target’s location in $P$, (1) compute a route that achieves a given
detection probability within the minimum amount of time, where the target is
detected if the watchman can see it; and (2) (dual to (1)) for a given time
budget $T$, compute a search route maximizing the probability of detecting the
target by time $T$. Denote by $\mu(.)$ the probability measure on all subsets
of $P$; $\mu(P_{1})$ is the probability measure of $P_{1}\subseteq P$, i.e the
probability that the target is in $P_{1}$, then

  * •

$0\leq\mu(.)\leq 1,\mu(\varnothing)=0,\mu(P)=1$,

  * •

$\mu(P_{1}\cup P_{2})=\mu(P_{1})+\mu(P_{2})$ if $P_{1}\cap P_{2}=\varnothing$.

We assume that we have access to $\mu(.)$ via an oracle: Given a triangular
region in $P$, the oracle returns its probability measure in $O(1)$ time.
Thus, for a point or a segment, the probability measure of its visibility
region can be computed in $O(n)$ time. Furthermore, if the watchman has
constant speed, a time constraint/objective is equivalent to that of length.
An optimal search route for each problem can be computed using the algorithms
given with probability measure instead of area.

## 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] Efim M. Bronshteyn and L. D. Ivanov.  The approximation of convex sets by polyhedra.  Siberian Mathematical Journal, 16(5):852–853, 1975.
  * [3] Kevin Buchin, Valentin Polishchuk, Leonid Sedov, and Roman Voronov.  Geometric secluded paths and planar satisfiability.  In 36th International Symposium on Computational Geometry (SoCG 2020). Schloss Dagstuhl-Leibniz-Zentrum für Informatik, 2020.
  * [4] John Canny.  The complexity of robot motion planning.  MIT press, 1988.
  * [5] 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.
  * [6] Bernard Chazelle.  Triangulating a simple polygon in linear time.  Discrete & Computational Geometry, 6(3):485–524, 1991.
  * [7] Chandra Chekuri and Martin Pal.  A recursive greedy algorithm for walks in directed graphs.  In 46th annual IEEE symposium on foundations of computer science (FOCS’05), pages 245–253. IEEE, 2005.
  * [8] Ke Chen and Sariel Har-Peled.  The Euclidean orienteering problem revisited.  SIAM Journal on Computing, 38(1):385–397, 2008.
  * [9] Otfried Cheong, Alon Efrat, and Sariel Har-Peled.  Finding a guard that sees most and a shop that sells most.  Discrete & Computational Geometry, 37:545–563, 2007.
  * [10] Wei-Pang Chin and Simeon Ntafos.  Optimum watchman routes.  In Proceedings of the second annual symposium on Computational geometry, pages 24–33, 1986.
  * [11] Wei-Pang Chin and Simeon Ntafos.  Shortest watchman routes in simple polygons.  Discrete & Computational Geometry, 6(1):9–31, 1991.
  * [12] Timothy H. Chung, Geoffrey A. Hollinger, and Volkan Isler.  Search and pursuit-evasion in mobile robotics: A survey.  Autonomous robots, 31:299–316, 2011.
  * [13] Moshe Dror, Alon Efrat, Anna Lubiw, and Joseph S. B. Mitchell.  Touring a sequence of polygons.  In Proceedings of the thirty-fifth annual ACM symposium on Theory of computing, pages 473–482, 2003.
  * [14] Richard M. Dudley.  Metric entropy of some classes of sets with differentiable boundaries.  Journal of Approximation Theory, 10(3):227–236, 1974.
  * [15] Adrian Dumitrescu, Joseph S. B. Mitchell, and Pawel Żyliński.  The minimum guarding tree problem.  Discrete Mathematics, Algorithms and Applications, 6(01):1450011, 2014.
  * [16] Adrian Dumitrescu, Joseph S. B. Mitchell, and Paweł Żyliński.  Watchman routes for lines and line segments.  Computational Geometry, 47(4):527–538, 2014.
  * [17] Adrian Dumitrescu and Csaba D. Tóth.  Watchman tours for polygons with holes.  Computational Geometry, 45(7):326–333, 2012.
  * [18] James N. Eagle.  The optimal search for a moving target when the search path is constrained.  Operations research, 32(5):1107–1115, 1984.
  * [19] James N. Eagle and James R. Yee.  An optimal branch-and-bound procedure for the constrained path, moving target search problem.  Operations research, 38(1):110–114, 1990.
  * [20] Lee-Ad Gottlieb, Robert Krauthgamer, and Havana Rika.  Faster algorithms for orienteering and k-tsp.  Theoretical Computer Science, 914:73–83, 2022.
  * [21] 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 second annual symposium on computational geometry, pages 1–13, 1986.
  * [22] Leonidas J. Guibas, Jean-Claude Latombe, Steven M. LaValle, David Lin, and Rajeev Motwani.  Visibility-based pursuit-evasion in a polygonal environment.  In Algorithms and Data Structures: 5th International Workshop, WADS’97 Halifax, Nova Scotia, Canada August 6–8, 1997 Proceedings 5, pages 17–30. Springer, 1997.
  * [23] Sariel Har-Peled and Mitchell Jones.  Proof of Dudley’s convex approximation.  arXiv preprint arXiv:1912.01977, 2019.
  * [24] Joseph S. B. Mitchell.  Geometric shortest paths and network optimization.  Handbook of computational geometry, 334:633–702, 2000.
  * [25] Joseph S. B. Mitchell.  Approximating watchman routes.  In Proceedings of the twenty-fourth annual ACM-SIAM symposium on Discrete algorithms, pages 844–855. SIAM, 2013.
  * [26] Simeon Ntafos and Markos Tsoukalas.  Optimum placement of guards.  Information sciences, 76(1-2):141–150, 1994.
  * [27] Joseph O’Rourke.  Visibility.  In Handbook of discrete and computational geometry, pages 875–896. Chapman and Hall/CRC, 2017.
  * [28] Erez Petrank.  The hardness of approximation: Gap location.  Computational complexity, 4:133–157, 1994.
  * [29] Michael Ian Shamos.  Computational geometry. Yale University, 1978.
  * [30] Xuehou Tan.  Fast computation of shortest watchman routes in simple polygons.  Information Processing Letters, 77(1):27–33, 2001.
  * [31] Xuehou Tan, Tomio Hirata, and Yasuyoshi Inagaki.  Corrigendum to" an incremental algorithm for constructing shortest watchman routes".  International Journal of Computational Geometry & Applications, 9(03):319–323, 1999.
  * [32] K. E. Trummel and J. R. Weisinger.  The complexity of the optimal searcher path problem.  Operations Research, 34(2):324–327, 1986.

##  Appendix A Hardness proofs

###  A.1 Simple polygons

We use a reduction from Inverse Knapsack, which is known to be NP-hard, to
show that QWRP is NP-hard, even in a simple polygon. Consider an instance of
Inverse Knapsack: Given a value quota $V$, items of integral weights
$(l_{1},\ldots,l_{m})$, and values $(V_{1},\ldots,V_{m})$, we are to determine
a combination of items having minimum total weight such that their collective
value is at least $V$.

We construct a polygon similar to what is shown on the right of Figure 9. The
construction is built from several “roof” gadgets (see Figure 9, left). Each
gadget consists of a rectangle of side lengths $\delta$ and $3\delta$, where
$\delta\ll\frac{1}{1000m}\min\\{l_{i}\\}$ and two wings of area $V_{i}$ in
total. To see both wings, the watchman needs to visit a point in the middle of
the rectangle. If the watchman chooses to visit only the bottom of the
rectangle instead, there will be a savings of at most $\delta$ in distance
travelled. Additionally, there are roofs with large area
$V_{\max}\gg\sum_{i=1}^{m}{V_{i}}$. Along the boundary of this polygon are $m$
roof gadgets of areas $V_{1},\ldots V_{m}$, each neighbors two gadgets of area
$V_{\max}$. We let $V_{c}$ denote the area of the remaining portion of the
polygon without the $V_{\max}$ gadgets and the wings of the $V_{i}$ gadgets.
Traveling from one gadget of area $V_{\max}$ to another of the same area
requires a cost of about $l_{0}\gg B$. If the watchman detours to visit a
rectangle of some $V_{i}$ roof, he must travel an additional distance of at
least $l_{0}+l_{i}-\delta$. We give the watchman a quota of
$V_{c}+mV_{\max}+V$. Since the $V_{\max}$ gadgets provide very large profits,
the tour has to visit all of them, as well as a subset of the remaining roofs
whose total area is at least $V$. Note that the tour does not necessarily
commit to seeing all gadgets chosen completely. However, by design, the
difference in distance traveled between seeing the gadgets “completely” and
“partially” is at most $m\delta\ll\frac{1}{1000}\min\\{l_{i}\\}$ and thus, the
watchman must necessarily select a subset of roofs that minimizes the total
detour length.

Given a tour that sees $V_{c}+mV_{\max}+V$, we can convert it to a solution
for the Inverse Knapsack instance with profit at least $V$ by looking at the
set of roofs the watchman visits other than the ones with $V_{\max}$ area.
Conversely, given an Inverse Knapsack solution that has profit $V$, we can
create a tour that sees area at least $V_{c}+mV_{\max}+V$. The above
construction is for the floating version of QWRP; to show that the anchored
version is also NP-hard, we simply use the same gadgets and place the starting
point in the gap of any $V_{\max}$ roof.

As for the BWRP, consider an instance of Knapsack with budget $B$ and the same
item weights and values as the Inverse Knapsack instance. We employ the same
construction and give the watchman a budget of $ml_{0}+B$. If we can compute a
route of length $ml_{0}+B$ with the maximum visibility area in polynomial
time, then we can compute a combination of items of total weight no greater
than $B$ maximizing the total value in polynomial time. Thus, the BWRP is NP-
hard.

Figure 9: Left: The roof gadgets (the $V_{i}$ gadget above and the $V_{\max}$
gadget below) used in the hardness proof for the QWRP and the BWRP. Note that
the illustration is not drawn to scale. Right: The red tour has length
$ml_{0}$; it is a shortest tour visiting all of the $V_{\max}$ gadgets. By
making a detour of length at least $l_{i}-\delta$, an additional area $V_{i}$
can be seen. The detour choices are independent of each other, due to the
$V_{\max}$ gadgets that isolate them.

###  A.2 Polygons with holes

####  A.2.1 Proof of Theorem 6.1

In [25], Mitchell proved there exists no polynomial time approximation
algorithm with a factor of $c\log n$ or better for some constant $c>0$, unless
P = NP. Since the WRP is a special case of the QWRP, in which the area quota
is the area of whole polygonal domain, a similar lower bound of approximation
is implied.

####  A.2.2 Proof of Theorem 6.2

Our proof is based on a reduction from the Max $k$-Vertex Cover problem in
cubic graphs: Given a graph $G=(V,E)$ where every node has degree 3, and a
positive integer $k$, find a subset of $k$ nodes such that the number of edges
incident with at least a node in the subset is maximized. Petrank proved in
[28] that unless P = NP, there is no polynomial time algorithm that
approximates the Max $k$-Vertex Cover problem in cubic graphs to a factor of
$1-\varepsilon$ for arbitrarily small $\varepsilon>0$.

We construct an instance of the BWRP in a polygon with holes $P$ as depicted
in Figure 10 (not to scale).

Figure 10: Reduction from the Max $k$-Vertex Cover problem in cubic graphs.

Black segments represent narrow corridors. From the bottom corridor of length
$l\ll 1$, there are $n$ small vertical corridors each of height $1$; these are
the node gadgets. Black circles, spaced evenly along a horizontal width $w$ at
height $H$, represent edges. If an edge and a node are incident in $G$, we
connect them accordingly with a triangular corridor. Each black circle is
connected to exactly two node gadgets, and an edge gadget is the rhombus-
shaped intersection of two triangular corridors. The bottom corridor, as well
as the node gadgets, have infinitesimal width and negligible area. We align
the edge gadgets so that they can only be seen from the top of a node gadget.

For an edge gadget $e_{j}$ incident with node gadget $v_{i}$, let
$\alpha_{ij}$ be the angle of the triangular corridor connecting $v_{i}$ and
$e_{j}$ at (the top of) $v_{i}$. We adjust the width $w$ along which and the
height $H$ at which the edge gadgets are placed as well as the angles
$\alpha_{ij}$’s so that

  * •

The triangular regions in node-edge corridors that are seen by only one node
gadget incident with the edge gadget (shaded gray in Figure 10) have constant
area $a$.

  * •

The smallest angle $\alpha_{ij}$ is no smaller than a constant (small) angle
$\overline{\alpha}$.

  * •

While corridors connecting different edge gadgets to different node gadgets
can cross (we place the edge gadgets so that no three corridors intersect at a
common area; thus, an intersection is only seen twice), the lowest crossing is
at a height greater than the budget $B$. Additionally, the highest crossing
must happen far away from the edge gadgets, so that total area of all
crossings ($O(k^{2})$ of them) is minuscule compared to the area of one edge
gadget, in particular the total area of all crossing should be no greater than
$\varepsilon b$.

The requirements above can be satisfied by making $H$ and $w$ arbitrarily
large.

Now, each edge gadget may have a different area, let $b$ be the minimum area
of any edge gadget. Note that by trigonometry
$b=\Theta(\sin(\alpha_{ij})a)=\Theta(\sin(\overline{\alpha})a)=\Theta(a)$. To
complete our construction, we cut off a small part from the top of each edge
gadget with area more than $b$ (however, we have to keep the $a$ areas
intact), as illustrated in Figure 10, to ensure all edge gadgets have the same
area. The construction can clearly be done in polynomial time.

We give the watchman a budget of $B=2l+2k$. If the watchman starts at (or
near) any edge gadget, he can only see an area of $b+2a$. If the watchman
starts in the middle of any node-edge corridor, he must travel down to the
node gadget, the bottom corridor and then other node gadgets to see more of
$P$. The watchman does not see any more area of $P$ when traveling down from a
node-edge corridor to the node gadget; as a result, we can impose that the
watchman must start somewhere in the region of the bottom corridor and the
node gadgets.

If an optimal solution of the Max $k$-Vertex Cover instance covers $m$ edges,
an optimal solution of the BWRP instance travels the bottom corridor,
selectively goes up some node gadgets to see an area of $3ka+mb$, minus the
area of the crossings between corridors. Suppose we have a polynomial-time
algorithm that approximates the BWRP to a factor of $(1-\varepsilon)$, run
that algorithm on $P$ and let $m^{\prime}$ be the number of edge gadgets the
approximate solution sees. Also, let $A_{1}$ be the total area of crossings of
corridors visible to node gadgets selected by the approximate solution, and
$A_{2}$ be that by the optimal solution, clearly
$A_{1}-(1-\varepsilon)A_{2}\geq\leavevmode\nobreak\ -\varepsilon b$. Hence,

$\displaystyle 3ka+m^{\prime}b-A_{1}$
$\displaystyle\geq(1-\varepsilon)(3ka+mb-A_{2})$ $\displaystyle\Leftrightarrow
3ka+m^{\prime}b$ $\displaystyle\geq(1-\varepsilon)(3ka+mb)-\varepsilon b$
$\displaystyle\Leftrightarrow 3\varepsilon ka+m^{\prime}b$
$\displaystyle\geq(1-\varepsilon)mb-\varepsilon b,$

moreover, since $m\geq m^{\prime}\geq k\geq 1$ and $b=\Theta(a)$

$\displaystyle O(1)\varepsilon mb+m^{\prime}b$
$\displaystyle\geq\left(1-2\varepsilon\right)mb$ $\displaystyle\Leftrightarrow
m^{\prime}$ $\displaystyle\geq(1-O(1)\varepsilon)m.$

Thus, the nodes selected by the aforementioned approximate solution to the
BWRP instance is a $(1-\varepsilon^{\prime})$-approximation, for some
$\varepsilon^{\prime}>0$ arbitrarily small, to the Max $k$-Vertex Cover
instance. This leads to a contradiction, and our proof of APX-hardness of the
BWRP in a polygon with holes is complete.

##  Appendix B Analysis of running times

###  B.1 Dual approximation algorithm for anchored QWRP, Theorem 2.11

We triangulate $P$ in $O(n)$ time, then compute all intersections between
polygon edges, diagonals of the triangulation and horizontal/vertical segments
of the square grid. We bound the number of candidate turn points by
$|S_{\delta,L}|=O\left(n+\frac{n}{\varepsilon_{1}}\cdot\frac{n}{\varepsilon_{1}}+\frac{n}{\varepsilon_{1}}\cdot
n+\frac{n}{\varepsilon_{1}}\cdot
n\right)=O\left(\frac{n^{2}}{\varepsilon_{1}^{2}}\right)$. After sorting the
candidates by geodesic angular order, we compute and store, for each candidate
$s_{i}$, $V(\pi_{P}(s,s_{i}))$. This can be done in $O(n)$ per candidate point
recursively. Start by computing and storing $V(ss_{i})$ for every child
$s_{i}$ of $s$ in $\mathcal{T}$. Then, for each internal node $s_{j}$, compute
the visibility polygon of the segment between $s_{j}$ and its parent node
$p(s_{j})$ in $O(n)$ time, and merge it with $V(\pi_{P}(s,p(s_{j}))$ (which is
a polygon with at most $n$ vertices) in $O(n)$ time. This allows us to compute
$V(s_{i}s_{j})\setminus V(\pi_{P}(s,s_{i}))$, for all pairs of candidates
$s_{i},s_{j}$ that see each other, in
$O\left(\frac{n^{5}}{\varepsilon_{1}^{4}}\right)$ time, which clearly
dominates the running time of computing and sorting $S_{\delta,L}$. Computing
a starting lower bound to $|\gamma|$ for the doubling search using the
visibility wave method takes $O(n^{2}\log n)$ time.

For each iteration of the doubling search, we run the dynamic programming
algorithm in which a subproblem is defined by a candidate point and a quota
value, hence there are $O\left(\frac{n^{2}}{\varepsilon_{1}^{2}}\right)\cdot
O\left(\frac{n}{\varepsilon_{1}\varepsilon_{2}}\right)=O\left(\frac{n^{3}}{\varepsilon_{1}^{3}\varepsilon_{2}}\right)$
subproblems. Each subproblem can be solved by recursing through
$O\left(\frac{n^{2}}{\varepsilon_{1}^{2}}\right)$ previously solved
subproblems and computing the area of visibility according to the Bellman
recursion which takes $O(1)$ for each since we have all
$V(s_{i}s_{j})\setminus V(\pi_{P}(s,s_{i}))$ pre-computed. Thus the overall
running time is $O\left(\frac{n^{5}}{\varepsilon_{1}^{5}\varepsilon_{2}}\log
n\right)$.

When $s$ is interior to $P$, recall that an optimal tour
$\gamma=(s,w_{1},w_{2},\ldots,w_{k},s)$ can be made relatively convex by
replacing $sw_{1}$ and $w_{k}s$ with $\pi_{P}(w_{1},w_{k})$. Thus we add a
factor of $O\left(\frac{n^{4}}{\varepsilon_{1}^{4}}\right)$ to the running
time by iterating over all pairs $(w_{1},w_{k})$, and finding a relatively
convex chain $C$ from $w_{1}$ to $w_{k}$ minimizing $|C|+|sw_{1}|+|sw_{2}|$
while $|V(C)\cup V(sw_{1})\cup V(sw_{2})|\geq A$.

###  B.2 Approximation algorithm for anchored BWRP, Theorem 3.4

The analysis of the running time of the dynamic program for the BWRP can be
done almost identically to that of the dual approximation algorithm for the
QWRP. A subproblem is defined by a candidate point and a budget value,
resulting in $O\left(\frac{n^{3}}{\varepsilon^{4}}\right)$ subproblems in
total, each of which can be solved in
$O\left(\frac{n^{2}}{\varepsilon^{2}}\right)$ time. The doubling search is not
required, since the budget value gives the size of the bounding box of the
route. We obtain a running time of
$O\left(\frac{n^{5}}{\varepsilon^{6}}\right)$ for the dynamic program for the
BWRP if a starting point $s$ is given on the boundary, and
$O\left(\frac{n^{9}}{\varepsilon^{10}}\right)$ if $s$ is interior to $P$.

###  B.3 FPTAS for anchored QWRP, Theorem 3.5

We first obtain a lower bound on $|\gamma|$ by computing the minimum radius
$r_{min}$ of a geodesic ball seeing at least the area quota $A$; let
$L:=r_{min}$. Perform a binary search on the values $\displaystyle
0,\frac{L}{\lceil\frac{2}{\varepsilon}\rceil},\frac{2L}{\lceil\frac{2}{\varepsilon}\rceil},\ldots,L$,
as choices for the input budget to the algorithm for the anchored BWRP with a
budget stretch of $(1+\varepsilon)$. In
$O\left(\frac{n^{5}}{\varepsilon^{6}}\log\frac{1}{\varepsilon}\right)$ time if
the starting point $s$ is on $\partial P$ or
$O\left(\frac{n^{9}}{\varepsilon^{10}}\log\frac{1}{\varepsilon}\right)$ if $s$
is interior to $P$, we can find a budget value for which the algorithm returns
a tour with visibility area greater than the quota $A$, if there is one. If no
such value exists, set $L:=2L$ and repeat the binary search. Ultimately, we
find a $(1+\varepsilon)^{2}$-approximation to the QWRP. Let
$2\varepsilon+\varepsilon^{2}=\varepsilon^{\prime}$, then
$\frac{1}{\varepsilon}=\Theta\left(\frac{1}{\varepsilon^{\prime}}\right)$ as
$\varepsilon$ and $\varepsilon^{\prime}$ approach 0. Thus in total running
time of $O\left(\frac{n^{5}}{\varepsilon^{\prime 6}}\log
n\log\frac{1}{\varepsilon^{\prime}}\right)$ or
$O\left(\frac{n^{9}}{\varepsilon^{\prime 10}}\log
n\log\frac{1}{\varepsilon^{\prime}}\right)$ depending on the location of $s$,
we can compute a $(1+\varepsilon^{\prime})$-approximate solution to the QWRP.

###  B.4 Exact algorithm for QWRP and BWRP in an arrangement of lines, Theorem
5.3

Since there are $n$ lines, there are $O(n^{2})$ vertices in
$V(\mathcal{A}(\mathcal{L}))$. We pre-compute $\pi(v_{i},v_{j})$ for all pairs
$v_{i},v_{j}$ in $O(n^{6})$ time and store them for faster access during the
algorithm. Also, pre-computing and storing
$|\mathcal{L}_{i,j}\setminus\mathcal{L}_{k,i}|$ for all triples of vertices
take $O(n^{7})$ time.

To solve the quota intersecting convex hull problem, for each of the
$O(n^{2})$ choices of $v_{1}$, we sort the vertices above $v_{1}$ in
$O(n^{2}\log n)$ time. There are $O\left(n^{3}\right)$ subproblems ($O(n^{2})$
vertices above $v_{1}$ and $n$ values of the quota) once we fix $v_{1}$. A
subproblem can be solved in $O(n^{2})$ time, which includes considering all
subproblems of lower indices and solving the Bellman recursion for each, which
takes constant time, since we have all
$|\mathcal{L}_{i,j}\setminus\mathcal{L}_{k,i}|$ and $\pi(v_{i},v_{j})$ pre-
computed. Thus, in $O\left({n^{7}}\right)$ time, we can obtain a solution to
the QWRP.

In terms of the BWRP (with given length budget $B$), we solve the QWRP with
the quota $Q=n$. Then, simply perform a binary search over all solved
subproblems $(v_{m},\overline{Q})$ with $\overline{Q}=1,2,\ldots,n$, return
the first value of $\overline{Q}$ such that $\pi(v_{m},\overline{Q})\leq
B,\pi(v_{m},\overline{Q}+1)>B$ and the associated cyclic sequence. Hence, the
BWRP in an arrangement of lines can also be solved in $O(n^{7})$ time.