# Observation Routes and External Watchman Routes

Adrian Dumitrescu Algoresearch L.L.C., Milwaukee, WI, USA. Email:
<EMAIL_ADDRESS>Csaba D. Tóth Department of Mathematics,
California State University Northridge, Los Angeles, CA; and Department of
Computer Science, Tufts University, Medford, MA, USA. Email:
<EMAIL_ADDRESS>Research on this paper was supported, in part, by the NSF
awards DMS-1800734 and DMS-2154347.

###### Abstract

We introduce the Observation Route Problem (ORP) defined as follows: Given a
set of $n$ pairwise disjoint compact regions in the plane, find a shortest
tour (route) such that an observer walking along this tour can see (observe)
some point in each region from some point of the tour. The observer does _not_
need to see the entire boundary of an object. The tour is _not_ allowed to
intersect the interior of any region (i.e., the regions are obstacles and
therefore out of bounds). The problem exhibits similarity to both the
Traveling Salesman Problem with Neighborhoods (TSPN) and the External Watchman
Route Problem (EWRP). We distinguish two variants: the range of visibility is
either limited to a bounding rectangle, or unlimited. We obtain the following
results:

(I) Given a family of $n$ disjoint convex bodies in the plane, computing a
shortest observation route does not admit a $(c\log n)$-approximation unless
$\P=\NP$ for an absolute constant $c>0$. (This holds for both limited and
unlimited vision.)

(II) Given a family of disjoint convex bodies in the plane, computing a
shortest external watchman route is $\NP$-hard. (This holds for both limited
and unlimited vision; and even for families of axis-aligned squares.)

(III) Given a family of $n$ disjoint fat convex polygons, an observation tour
whose length is at most $O(\log{n})$ times the optimal can be computed in
polynomial time. (This holds for limited vision.)

(IV) For every $n\geq 5$, there exists a convex polygon with $n$ sides and all
angles obtuse such that its perimeter is _not_ a shortest external watchman
route. This refutes a conjecture by Absar and Whitesides (2006).

##  1 Introduction

Path planning and visibility are two central areas in computational geometry
and robotics. In path planning, a short collision-free path between two
specified points is desired, and the robot has to see or detect obstacles in
order to avoid them in its path. Hence there is a close relation between short
paths and visibility. Moreover, visibility of an object (say, an obstacle) can
be accomplished at various degrees; for instance, sometimes it may suffice to
simply detect the presence of an obstacle, and other times the robot may need
to map or recognize (e.g., see) the entire boundary of an obstacle in order to
select a meaningful action.

In the Traveling Salesman with Neighborhoods problem (TSPN), given a set of
regions (neighborhoods) in the plane, one is to compute a shortest closed
route (tour) that visits each neighborhood; whereas in the External Watchman
Route Problem (EWRP), given a set of disjoint regions in the plane, one is to
compute a shortest closed route (tour) in the exterior of a region (i.e., in
the _free space_) so that every point on the boundary of every region is
visible from some point of the tour. These problems were posed about three
decades ago by Arkin and Hassin [3] and by Ntafos and Gewali [39],
respectively. A small example that illustrates ORP and EWRP appears in Fig. 1.
Here we introduce the following related problem we call the Observation Route
Problem (ORP):

> ORP: Given a set of $n$ pairwise disjoint compact regions in the plane, find
> a shortest route (tour) such that an observer going along this tour can see
> (observe) each of the regions from at least one point of the tour. The tour
> cannot enter the interior of any region.

Figure 1: An observation route (the blue point) and an external watchman route
(dotted, in red) for a set of five triangles.

#### Related work.

In the Euclidean Traveling Salesman problem (ETSP), given a set of points in
the plane (or in the Euclidean space $\mathbb{R}^{d}$, $d\geq 3$), one seeks a
shortest tour (closed curve) that visits each point. In the _TSP with
neighborhoods_ (TSPN), each point is replaced by a (possibly disconnected)
region [3]. The tour must visit at least one point in each of the given
regions (i.e., it must intersect each region). Since ETSP is $\NP$-hard in
$\mathbb{R}^{d}$ for every $d\geq 2$ [23, 24, 42], TSPN is also $\NP$-hard for
every $d\geq 2$.

At about the same time, Arora [4] and Mitchell [31] independently showed that
ETSP in $\mathbb{R}^{d}$, for constant $d$, admits a polynomial-time
approximation scheme (PTAS). In contrast, TSPN is harder to approximate and
certain instances are known to be $\APX$-hard. However, better approximations
can be obtained for neighborhoods with “nice” geometric properties: connected,
pairwise disjoint, or fat, or of comparable sizes, etc. Arkin and Hassin [3]
gave constant-factor approximations for translates of a connected region;
Dumitrescu and Mitchell [16] extended the above result to connected
neighborhoods of comparable diameters.

For $n$ connected (possibly overlapping) neighborhoods in the plane, TSPN can
be approximated with ratio $O(\log{n})$ by the algorithms of (i) Mata and
Mitchell [30], (ii) Gudmundsson and Levcopoulos [26], and (iii) Elbassioni,
Fishkin, and Sitters [20]. The $O(\log{n})$-approximation stems from the
following early result by Levcopoulos and Lingas [28]: Every (simple)
rectilinear polygon $P$ with $n$ vertices, $r$ of which are reflex, can be
partitioned in $O(n\log{n})$ time into rectangles whose total perimeter is
$\log{r}$ times the perimeter of $P$. We will use any of the three algorithms
mentioned above as a subroutine in our approximation algorithm for ORP in
Section 3.

In the Watchman Route Problem (WRP), given a polygonal domain $P$, the goal is
to find a shortest closed curve within $P$ such that every point of $P$ is
seen from some point along the curve. Thus WRP is dual to EWRP in the sense
that the former deals with the interior of a polygonal domain whereas the
latter deals with the exterior of one or more polygons. The watchman route
problem in a simple polygon $P$ first considered by Chin and Ntafos as early
as 1986 [7, 8, 9]. After more than one decade of being in a tangle [6, 46,
47], its polynomial status appears to have been settled by Tan et al. [48].
The current fastest algorithm, running in $O(n^{4}\log{n})$ time, is due to
Dror et al. [12]. A linear-time 2-approximation algorithm is due to Tan [47].
Ntafos and Gewali [39] showed that a shortest external watchman route for a
$n$-vertex convex polygon can be found in $O(n)$ time. The case of two convex
polygons was studied in [25]. The first polynomial-time approximation
algorithm for the watchman route problem in $n$-vertex polygons with holes was
given by Mitchell [33]; its approximation ratio is $O(\log^{2}{n})$. Nilsson
and Żyliński [37] showed that computing a shortest tour that sees $k$
specified points in a polygon with $h$ holes is fixed parameter tractable
(FPT) with the parameter $h+k$, but the problem in general cannot be
polynomially approximated better than by a factor of $c\log n$ for some
constant $c>0$, unless $\P=\NP$.

Regarding the degree of approximation achievable, TSPN for arbitrary
neighborhoods is $\APX$-hard [10, 44], and approximating TSPN for connected
regions in the plane within a factor smaller than 2 is intractable
($\NP$-hard) [44]. The problem is also $\APX$-hard for disconnected regions
[44], the simplest case being point-pair regions [13]. It is conjectured that
approximating TSPN for disconnected regions in the plane within a
$O(\log^{1/2}n)$ factor is intractable [44]. Computing the minimum number of
point guards, vertex guards, or edge guards, are all $\APX$-hard [19] and
finding the minimum number of point guards is $\exists\mathbb{R}$-complete
[1], even for simple polygons (without holes). That is, there is a constant
$\delta>0$ such that no polynomial-time algorithm achieves an approximation
ratio of $1+\delta$ for any of these problems unless $\P=\NP$. The survey by
Urrutia [49] gives an introduction to these problems. See also [5] and [27]
for recent approximations and parameterized hardness results. Historically,
watchman routes under limited visibility have been considered by Ntafos [38];
see also [32, 34] for a survey of the many variants of WRP. other variants are
discussed in [32, 34]. As mentioned earlier, the problem of computing shortest
_external_ watchman routes for collections of disjoint polygons was suggested
by Ntafos and Gewali [39].

#### Definitions and notations.

A curve is called _simple_ if it has no self-intersections. A _simple polygon_
$P$ is a polygon without holes, that is, the interior of the polygon is
topologically equivalent to a disk. A _polygon with holes_ is obtained by
removing a set of nonoverlapping, strictly interior, simple subpolygons from
$P$ [41]. The Euclidean length of a curve $\gamma$ is denoted by ${\rm
len}(\gamma)$, or just $|\gamma|$ when there is no danger of confusion.
Similarly, the total (Euclidean) length of the edges of a geometric graph $G$
or a polygon $P$ is denoted by ${\rm len}(G)$ and ${\rm per}(P)$,
respectively.

A TSP tour for a set $\mathcal{F}$ of regions (neighborhoods) in
$\mathbb{R}^{d}$, $d\geq 2$, is a closed curve in the ambient space that
intersects $\mathcal{F}$ (i.e., $\gamma$ intersects each region in
$\mathcal{F}$). For $\alpha\geq 1$, an approximation algorithm (for ORP, EWRP,
or TSPN) has ratio $\alpha$ if its output tour ALG satisfies ${\rm
len}(\textsf{ALG})\leq\alpha\,{\rm len}(\textsf{OPT})$, where OPT is an
optimal tour for the respective problem.

A _convex body_ $C\subset\mathbb{R}^{d}$ is a compact convex set with nonempty
interior. Its _boundary_ is denoted by $\partial C$ and its _interior_ by
$\mathring{C}$. The _width_ of a convex body $C$ is the minimum width of a
strip of parallel lines enclosing $C$. Informally, a convex body is _fat_ if
its width is comparable with its diameter. More precisely, for
$0\leq\lambda\leq 1$, a convex body $C$ is $\lambda$-_fat_ if its width $w$ is
at least $\lambda$ times the diameter: $w\geq\lambda\cdot{\rm diam}(C)$, and
$C$ is _fat_ if the inequality holds for a constant $\lambda$. For instance, a
square is $\frac{1}{\sqrt{2}}$-fat, a $3\times 1$ rectangle is
$\frac{1}{\sqrt{10}}$-fat and a segment is $0$-fat. Let $\gamma$ be a closed
curve. The _geometric dilation_ of $\gamma$ is

$\delta(\gamma):=\sup\limits_{p,q\in\gamma}\frac{d_{\gamma}(p,q)}{|pq|},$

where $d_{\gamma}(p,q)$ is the shortest distance along $\gamma$ between $p$
and $q$. For example, the geometric dilation of a the boundary of a square is
$2$ and that of a $3\times 1$ rectangle is $4$.

Points $p$ and $q$ are mutually _visible_ if the segment $pq$ does not
intersect the interior of any region in $\mathcal{F}$ [40]. An object
$O\in\mathcal{F}$ can be _seen_ (or _observed_) from a point $p$ if there is a
point $q\in\partial O$ such that $p$ and $q$ are mutually visible. The convex
hull of a set $A\subset\mathbb{R}^{d}$ is denoted by ${\rm conv}(A)$.

###  1.1 Our results

In Section 2, as a preliminary result, we show that given a set of convex
polygons $\mathcal{F}$, determining whether $\mathcal{F}$ can be observed from
a single point can be done by a polynomial time algorithm. In Section 3 we
show that given a set of $n$ pairwise disjoint fat convex polygons, an
observation tour whose length is at most $O(\log{n})$ times the optimal can be
computed in polynomial time. The algorithm reduces the ORP problem to TSPN for
polygons with holes and then executes additional local transformations of the
tour that only increase the total length by at most a constant factor. In
Subsection 3.1 we show that the case of translates (within the same class)
allows for a simplification in the algorithm.

######  Theorem 1.

Given a family of $n$ pairwise disjoint fat convex polygons, an observation
tour whose length is at most $O(\log{n})$ times the optimal can be computed in
polynomial time.

In Section 4, we prove the $\NP$-hardness of both ORP and EWRP for both
limited and unlimited vision (Theorems 2 and 3). Throughout this paper, the
term _limited vision_ refers to unrestricted vision in a given bounding box of
the family.

######  Theorem 2.

Given a family of disjoint convex bodies in the plane, computing a shortest
observation route is $\NP$-hard. (This holds for both limited and unlimited
vision.) The problem remains so even for families of axis-aligned squares.

######  Theorem 3.

Given a family of disjoint convex bodies in the plane, computing a shortest
external watchman route is $\NP$-hard. (This holds for both limited and
unlimited vision.) The problem remains so even for families of axis-aligned
squares.

In Section 5, we prove that one cannot approximate the minimum length of an
observation route for $n$ convex bodies in the plane within a factor of
$c\,\log n$, for some $c>0$, unless $\P=\NP$. The inapproximabilty is reduced
from Set Cover.

######  Theorem 4.

Given a family of $n$ disjoint convex bodies in the plane, the length of a
shortest observation route cannot be approximated within a factor of $c\,\log
n$ unless $\P=\NP$, where $c>0$ is an absolute constant. (This holds for both
limited and unlimited vision.)

In Section 6 we study the structure of shortest external watchman routes for a
convex polygon (i.e., $|\mathcal{F}|=1$). In 2006, Absar and Whitesides
conjectured that all convex polygons with all angles _obtuse_ have convex-hull
routes as their shortest external watchman routes [2]. Theorem 5 below refutes
this conjecture for every $n\geq 5$.

######  Theorem 5.

For every $n\geq 5$ there exists a convex polygon with $n$ sides and all
angles obtuse such that its perimeter is _not_ a shortest external watchman
route.

In Section 7 we compare the optimal solutions for the three problems discussed
(ORP, EWRP, and TSPN). While the lengths of the optimal tours for these
problems can differ substantially for a given input, we exhibit two natural
scenarios when they are roughly the same.

######  Theorem 6.

Consider the two scenarios below:

  1. (i)

Let $\mathcal{F}$ be a maximal packing of unit disks in a large square $S$.
(That is, one cannot extend this packing by adding new disks contained in
$S$). Then $\textsf{OPT}_{\textsf{ORP}}(\mathcal{F})=\Theta(n)$,
$\textsf{OPT}_{\textsf{EWRP}}(\mathcal{F})=\Theta(n)$, and
$\textsf{OPT}_{\textsf{TSPN}}(\mathcal{F})=\Theta(n)$.

  2. (ii)

Let $\mathcal{F}$ the family of axis-aligned squares in the $\NP$-hardness
reduction from a set of $n$ integer points in the proof of Theorem 2. Then
$\textsf{OPT}_{\textsf{TSPN}}(\mathcal{F})|\geq n$,
$|\textsf{OPT}_{\textsf{ORP}}(\mathcal{F})-\textsf{OPT}_{\textsf{TSPN}}(\mathcal{F})|<1$,
and
$|\textsf{OPT}_{\textsf{EWRP}}(\mathcal{F})-\textsf{OPT}_{\textsf{TSPN}}(\mathcal{F})|<1$.

##  2 Preliminaries

Throughout the paper we consider families of disjoint compact convex sets in
the plane; and are only concerned with _external_ visibility. See Fig. 2 for
an example.

Figure 2: Left: three convex polygons in a bounding box. Right: the visibility
region $V$ of the triangle is a polygon with two holes.

For a set $\mathcal{F}$ of $n$ disjoint polygons in a rectangle $R$, the
_visibility region_ of a polygon $P\in\mathcal{F}$, denoted $V(P)$, is the set
of all point $p\in R$ such that there exists a point $q\in\partial P$ such
that the line segment $pq$ is disjoint from $\overset{\circ}{P^{\prime}}$ for
all $P^{\prime}\in\mathcal{F}$.

######  Lemma 1.

Given a set $\mathcal{F}$ of $n$ disjoint convex polygons with a total of $m$
vertices in a rectangle $R$, for every $C\in\mathcal{F}$, the visibility
region $V(C)$ is a polygon with $O(m+n^{2})$ vertices and $O(n^{2})$ holes.

###### Proof.

Note that $C$ is always a hole of $V(C)$. The boundary of $V(C)$ is contained
in the union of the boundary of the free space
$R\setminus\bigcup_{C^{\prime}\in\mathcal{F}}C^{\prime}$ and all common inner
and outer tangents between $C$ and other polygons in $\mathcal{F}$.
Consequently, $V(C)$ is a polygon with $O(m+n^{2})$ vertices. Since the
polygons in $\mathcal{F}$ are disjoint, every hole of $V(C)$ has a vertex at
the intersection of two tangents or one tangent and the boundary $\partial
C^{\prime}$, $C^{\prime}\in\mathcal{F}\setminus\\{C\\}$. Now $O(n)$ tangents
and $O(n)$ convex curves yield $O(n^{2})$ intersections, and so the number of
holes in $V(C)$ is also $O(n^{2})$.

It remains to prove that $V(C)$ is connected. Let $p$ and $q$ be any two
points in $V(C)$. By definition, there exist $p^{\prime},q^{\prime}\in\partial
C$ such that $p^{\prime}$ is visible from $p$, and $q^{\prime}$ is visible
from $q$. Let $\rho(p^{\prime},q^{\prime})$ denote the shortest path
connecting $p^{\prime}$ and $q^{\prime}$ on the boundary of $C$. Then one can
reach $q$ from $p$ via the $3$-leg path that connects $p$ to $p^{\prime}$ via
a straight-line segment, follows $\rho(p^{\prime},q^{\prime})$ on $C$’s
boundary and connects $q^{\prime}$ to $q$ via a straight-line segment. ∎

Next we show that given a set $\mathcal{F}$ of convex polygons, one can
determine in polynomial-time whether all polygons in $\mathcal{F}$ can be
observed from a single point. Note that for the variant with unlimited
visibility, visibility regions may be unbounded. We need a simple lemma
regarding zero-instances of TSPN.

######  Lemma 2.

Given a family $\mathcal{F}$ of (possibly unbounded) polygonal regions with a
total of $m$ vertices, one can determine whether there exists a point
contained in all polygons in $\mathcal{F}$ (i.e., whether
$\textsf{OPT}_{\textsf{TSPN}}(\mathcal{F})=0$) in time polynomial in $m$.

###### Proof.

This is equivalent to determining whether the intersection
$\bigcap_{P\in\mathcal{F}}P$ is empty. Since the total complexity of the
visibility regions is polynomial in $m$, the complexity of the intersection is
also polynomial in $n$. Consequently, the resulting algorithm takes time
polynomial in $m$. ∎

Applying Lemma 2 to the visibility regions of the polygons in $\mathcal{F}$
immediately yields the following.

######  Corollary 1.

Given a set $\mathcal{F}$ of convex polygons with a total of $m$ vertices, one
can determine whether $\mathcal{F}$ can be observed from a single point (i.e.,
whether $\textsf{OPT}_{\textsf{ORP}}(\mathcal{F})=0$) in time polynomial in
$m$.

Lemma 3 below shows that optimizing the length of the route is sometimes
impractical as it may produce routes that are arbitrarily far from the
observed objects. However, we can enforce routes in the near vicinity of the
family to be observed by constraining the observation tour to lie in a
bounding box of the family (e.g., an axis-parallel rectangle).

######  Lemma 3.

For every $\Delta>0$, there exists a configuration
$\mathcal{F}=\mathcal{F}(\Delta)$ of $O(1)$ axis-parallel unit squares such
that: (i) ${\rm diam}({\rm conv}(\mathcal{F}))=O(1)$, (ii)
$\textsf{OPT}_{\textsf{ORP}}(\mathcal{F})=0$, i.e., the configuration can be
observed from a single point, and (iii) every single observation point is at a
distance at least $\Delta$ from ${\rm conv}(\mathcal{F})$. Alternatively,
$\mathcal{F}$ can be realized from unit disks.

###### Proof.

We exhibit and analyze a configuration (family $\mathcal{F}$) of six axis-
parallel unit squares; refer to Fig. 3. An analogous unit disk configuration
(with six elements) can be derived from a piece of the hexagonal disk packing
by slightly shrinking each disk from its center; its analysis is left to the
reader.

Figure 3: Left: This family can be only observed from single points far away
up or down. Right: This family can be observed from any single point on a
horizontal line that separates the upper chain of squares from the lower one.

Let $\varepsilon>0$ be sufficiently small, as specified below. Successive
squares (from left to right) are horizontally separated by $\varepsilon$ and
shifted vertically by $2\varepsilon$. Let $\ell$ be a horizontal line
separating the squares $B$ and $E$. Without loss of generality let $p$ be an
observation point on or above $\ell$. If $p$ lies inside ${\rm
conv}(\mathcal{F})$, depending on its position, either $C$ or $D$ is not
observable from $p$ (if $\varepsilon>0$ is sufficiently small). Suppose that
$p$ lies outside ${\rm conv}(\mathcal{F})$, and on or to the right of the
vertical axis of symmetry of $B$. Then $D$ is not observable from $p$ unless
$p$ is above the common internal tangent to $A$ and $B$ of positive slope and
above the common internal tangent to $B$ and $C$ of negative slope. These
tangents continuously depend on $\varepsilon$ and are almost vertical as
$\varepsilon$ tends to zero, hence the lowest point in the intersection of the
corresponding halfplanes can be arbitrarily high, as claimed. The case when
$p$ lies outside ${\rm conv}(\mathcal{F})$ on or to the left of the vertical
axis of symmetry of $B$ is similar. It is clear that one can always find a
suitable $\varepsilon=\varepsilon(\Delta)$, as required. ∎

The following lemma relates fatness to geometric dilation for closed curves:

######  Lemma 4.

Let $C$ be a $\lambda$-fat convex curve. Then
$\delta(C)\leq\min(\pi\lambda^{-1},2(\lambda^{-1}+1))$.

###### Proof.

If $C$ is a convex curve, it is known [18, Lemma 11] that
$\delta(C)=\frac{|C|}{2h}$. It is also known [14, Thm. 8] that $h\geq w/2$,
where $h=h(C)$ is the _minimum halving distance_ of $C$ (i.e., the minimum
distance between two points on $C$ that divide the length of $C$ in two equal
parts), and $w=w(C)$ is the width of $C$. Putting these together one deduces
that $\delta(C)\leq\frac{|C|}{w}$. Let $D$ denote the diameter of $C$. The
isoperimetric inequality $|C|\leq D\pi$ and the obvious inequality $|C|\leq
2D+2w$ lead to the following dilation bounds $\delta(C)\leq\pi\frac{D}{w}$ and
$\delta(C)\leq 2\left(\frac{D}{w}+1\right)$, see also [14, 45]. Since $C$ is
$\lambda$-fat, direct substitution yields the two bounds given in the lemma.
Note that the latter bound is better for small $\lambda$. ∎

##  3 Fat convex polygons

In this section we prove Theorem 1. The following algorithm computes a tour
for a family $\mathcal{F}=\\{C_{1},\ldots,C_{n}\\}$ of convex polygons in a
rectangle $R$.

Algorithm 1.

  * Step 1: Compute the visibility regions $V_{i}=V(C_{i})$, $i=1,\ldots,n$.

  * Step 2: Use the TSPN algorithm for connected regions as a subroutine (from [30],[26], or [20], as explained in Section 1) to obtain a $O(\log{n})$ approximation for a tour $T$ that visits all $V_{i}$, $i=1,\ldots,n$.

  * Step 3: Locally transform $T$ by making detours that avoid the elements $C_{i}\in\mathcal{F}$ that are crossed by $T$, if any. Specifically, for each $C\in\mathcal{F}$ that is intersected by $T$, replace the subpath $\varrho=C\cap T$ by the shortest path along $\partial C$ connecting the start and end points of $\varrho$; as shown in Fig. 4. Output the resulting tour $T^{\prime}$.

Figure 4: Local replacements to obtain $T^{\prime}$ from $T$.

#### Algorithm analysis.

By Lemma 1, all visibility regions $V_{i}=V(C_{i})$ are connected, and so
$\mathcal{F}$ represents a valid input for the TSPN algorithm. Recall that the
tour $T$ returned by the TSPN algorithm visits all visibility regions; this
means that each $C_{i}$ is seen from some point in
$T\setminus(\bigcup_{i=1}^{n}C_{i})$. The local replacements in Step 3 ensure
that the resulting tour $T^{\prime}$ does not intersect (the interior of) any
obstacle, and maintain the property that the tour visits all visibility
regions; i.e., each $C_{i}$ is seen from some point in
$T^{\prime}\setminus(\bigcup_{i=1}^{n}C_{i})$. Consequently, $T^{\prime}$ is
an observation route for $\mathcal{F}$. Since each region $V_{i}$ has
polynomial complexity by Lemma 1 (i.e., polynomial in the total number of
vertices of the polygons in $\mathcal{F}$), Algorithm 1 runs in polynomial
time.

It remains to bound ${\rm len}(T^{\prime})$ from above. Let
$\mathcal{V}=\\{V_{1},\ldots,V_{n}\\}$. An observation route for $\mathcal{F}$
must visit the visibility regions $V_{i}$ for all $i=1,\ldots,n$, and so
$\textsf{OPT}_{\textsf{TSPN}}(\mathcal{V})\leq\textsf{OPT}_{\textsf{ORP}}(\mathcal{F})$,
which implies

${\rm len}(T)\leq O(\textsf{OPT}_{\textsf{TSPN}}(\mathcal{V})\,\log n)\leq
O(\textsf{OPT}_{\textsf{ORP}}(\mathcal{F})\,\log n).$

Recall that all $C_{i}$ are fat and thus by Lemma 4, the local replacements in
Step 3 increase the length by at most a constant factor (that depends on
$\lambda=\Omega(1)$), that is, ${\rm len}(T^{\prime})\leq O({\rm len}(T))$.
This concludes the proof of Theorem 1.

###  3.1 Translates of a fat convex polygon

In this subsection we restrict ourselves to families of translates of a fat
convex body $C$. The visibility regions associated to the elements of
$\mathcal{F}$ are then restricted and this allows for a simplified input for
the algorithm. Specifically, Corollary 2 below shows that each visibility
region is a polygon with a unique hole (the convex body itself). The
approximation ratio remains the same.

######  Lemma 5.

Let $C$ be a convex body and let $op$ and $oq$ be the two tangent rays
incident to $o$ and $C$ so that $\angle{poq}$ is oriented counterclockwise.
Let $C^{\prime}$ be a translate of $C$ further away from $o$ that is tangent
to $op$ at $p^{\prime}$: that is, $C^{\prime}=C+\overrightarrow{pp^{\prime}}$.
Then the ray $oq$ does not intersect $C^{\prime}$.

###### Proof.

Assume for concreteness that $op$ is a horizontal line, and so the points
$o,p,p^{\prime}$ appear on the line in this order. Refer to Fig. 5.

Figure 5: Two translates of a convex polygon in a cone.

We may assume that $\angle{poq}$ is acute (since otherwise the claim is
obvious). Recall that $C^{\prime}=C+\overrightarrow{pp^{\prime}}$, and
consider the following continuous motion: $C$ moves right and so the contact
between $C$ and the ray $oq$ disappears right after the start of the motion.
Thus $C$ remains strictly below this ray throughout the translation and the
lemma follows. ∎

######  Lemma 6.

For every $C\in\mathcal{F}$ and every point $o\notin C\cup V(C)$, there exists
a ray $\vec{\rho}$ emanating from $o$ such that $\vec{\rho}$ is disjoint from
$C\cup V(C)$.

###### Proof.

Let $op$ and $oq$ be the two tangents to $C$ emanating from $o$ such that the
angle $\angle poq$ is oriented counterclockwise. See Fig. 6 (right) where the
angle is shaded. By Lemma 5, if a convex body $C^{\prime}\in\mathcal{F}$,
$C^{\prime}\neq C$, intersects the triangle $\Delta{poq}$, then $C^{\prime}$
intersects at least one of the line segments $op$ or $oq$. We distinguish
between two cases.

Figure 6: Illustrations for Lemma 6: Two possible choices for ray
$\vec{\rho}$.

Case 1: There exists a convex body $C^{\prime}\in\mathcal{F}$, $C^{\prime}\neq
C$, that intersects both $op$ and $oq$. Refer to Fig. 6 (left). Since
$C^{\prime}\in\mathcal{F}$, then $C^{\prime}=C+\vec{v}$ for some vector
$\vec{v}\in\mathbb{R}^{2}$. Both common external tangents of $C$ and
$C^{\prime}$ are parallel to $\vec{v}$, and so they bound a parallel strip
denoted by $S$. Let $\vec{\rho}$ be a ray emanating from $o$ in direction
$\vec{v}$. Then $\vec{\rho}$ lies in $S$, and $C^{\prime}$ separates $C$ from
$\vec{\rho}$ within $S$. Consequently, $\vec{\rho}$ is disjoint from $C\cup
V(C)$.

Case 2: There is no convex body $C^{\prime}\in\mathcal{F}$, $C^{\prime}\neq
C$, that intersects both $op$ and $oq$. See Fig. 6 (right). Since $o\notin
V(C)$, then $op$ intersects the interior of some body in $\mathcal{F}$. Let
$C_{p}$ be the translate in $\mathcal{F}$ that intersects $op$ and maximizes
the angle $\angle poq_{p}$, where $oq_{p}$ is a tangent ray to $C_{p}$.
Similarly, let $C_{q}$ be the translate in $\mathcal{F}$ that intersects $oq$
and maximizes the angle $\angle p_{q}oq$, where $op_{q}$ is a tangent ray to
$C_{q}$. Since $o\notin V(C)$, and for every $c\in\partial C$, the segment
$oc$ intersects the interior of some convex body in $\mathcal{F}$ that also
intersects $op$ or $oq$, then the clockwise angle $\angle q_{p}op_{q}$ is
nonzero. Let $\vec{u}$ be the direction vector of the angle bisector of
$\angle q_{p}op_{q}$, and let $\vec{\rho}$ be a ray emanating from $o$ in
direction $-\vec{u}$.

It remains to show that $\vec{\rho}$ is disjoint from $C\cup V(C)$. Assume
w.l.o.g. that $o$ is the origin and $\vec{\rho}$ is the negative $x$-axis. Let
$r$ be any point on $\vec{\rho}$. Consider the horizontal strip $S_{p}$
bounded by the two horizontal tangent lines to $C_{p}$. Note that this strip
contains the $x$-axis, and $C_{p}$ separates $\vec{\rho}$ from $C$ within
$S_{p}$. Consequently any line segment between $r$ and a point $c\in\partial
C$ below the $x$-axis intersects the interior of $C_{p}$. Similarly, any line
segment between $r$ and a point $c\in\partial C$ above the $x$-axis intersects
the interior of $C_{q}$. Overall, no point in $\vec{\rho}$ can see any point
on $\partial C$. This implies that $\vec{\rho}$ is disjoint from $C\cup V(C)$.
∎

######  Corollary 2.

For every $C\in\mathcal{F}$, the visibility region $V(C)$ is a polygon with
exactly one hole, namely $C$.

###### Proof.

It is clear that $C\in\mathcal{F}$ is a hole in $V(C)$, since every point in a
small neighborhood of $\partial C$ is in $V(C)$, but points in $C$ are not in
$V(C)$. Suppose, for contradiction, that $V(C)$ has another hole $H$, i.e., a
bounded connected component of $\mathbb{R}^{2}\setminus V(C)$. Let $p$ be an
arbitrary point in the interior of $H$. By Lemma 6, there is a ray
$\overrightarrow{r}$ emanating from $p$ that lies entirely in the exterior of
$V(C)$, hence in $H$. Consequently, $H$ is unbounded, which is a
contradiction. ∎

See Figure 7 for an example with a family of translates.

Figure 7: Left: a family of seven translates. Right: The visibility region of
the shaded translate is a polygon with one hole (in blue).

#### Visibility from a single point.

The algorithm in Corollary 1 can be further simplified for families of
translates of a convex polygon. Let $V_{i}=V(C_{i})$. Observe that $V_{i}\cup
C_{i}$ is a simple polygon (without holes). Since $\partial C_{i}\subset
V_{i}$, we have $V_{i}\cup C_{i}=V_{i}\cup\mathring{C_{i}}$. Moreover, we have
$V_{i}\cap\mathring{C_{j}}=\emptyset$ for every $i\neq j$. Consequently, by
using the distributivity of intersection over union we obtain

$\displaystyle(V_{i}\cup C_{i})\cap(V_{j}\cup C_{j})$
$\displaystyle=(V_{i}\cup\mathring{C_{i}})\cap(V_{j}\cup\mathring{C_{j}})$
$\displaystyle=(V_{i}\cap
V_{j})\cup(V_{i}\cap\mathring{C_{j}})\cup(V_{j}\cap\mathring{C_{i}})\cup(\mathring{C_{i}}\cap\mathring{C_{j}})$
$\displaystyle=(V_{i}\cap V_{j})\cup\emptyset\cup\emptyset\cup\emptyset$
$\displaystyle=V_{i}\cap V_{j}.$

Consequently, it suffices to work with simple polygons. Indeed,

$\bigcap_{i=1,\ldots,n}V_{i}=\bigcap_{i=1,\ldots,n}(V_{i}\cup C_{i}),$

and so it suffices to determine whether the intersection of the simple
polygons $(V_{i}\cup C_{i})$, $i=1,\ldots,n$, is non-empty.

##  4 $\NP$-hardness results

In this section we prove that both ORP and EWRP are $\NP$-hard. Both
reductions are from Rectilinear TSP (RTSP) assuming limited vision.
Essentially the same reductions also hold with unlimited vision. It is known
[23, 42] that both ETSP and RTSP are $\NP$-hard. The three relevant problems
ORP, ETSP, and RTSP (see [24, 42]) can be formulated as decision problems as
follows:

> ORP: Given a family $\mathcal{F}$ of $k$ polygonal regions and a positive
> integer $m$, does there exist an observation tour of Euclidean length at
> most $m$?

> ETSP: Given a set of $n$ points in the plane and a positive integer $m$,
> does there exist a tour of Euclidean length at most $m$ that visits all the
> points?

> RTSP: Given a set of $n$ points in the plane and a positive integer $m$,
> does there exist a tour of rectilinear length at most $m$ that visits all
> the points?

Figure 8: Left: point set $S$ in $R$. Middle: family of axis-aligned squares
in $B$. Right: a small cluster (gadget) $\G$ of $25$ disjoint congruent
squares for each point in $S$. The shaded square in the center of $\G$ cannot
be observed (or watched) without entering the convex hull ${\rm conv}(\G)$.

It is known from that ETSP is $\NP$-hard under both $L_{1}$\- and
$L_{2}$-norms [23, 42]. The $\NP$-hardness of WRP was first announced by Chin
and Ntafos [7, 8] via a reduction from ETSP under the $L_{2}$-norm. However,
the first valid proof, due to Dumitrescu and Tóth [17], makes a reduction from
RTSP. To show that ORP is $\NP$-hard, we use a reduction based on a similar
idea, as follows; refer to Fig. 8.

#### Proof of Theorem 2.

Given a set $S$ of $n$ points of the integer lattice $\mathbb{Z}^{2}$, assume
without loss of generality that the smallest axis-aligned rectangle containing
$S$ is $R=[0,a]\times[0,b]$, for some positive integers $a\geq b$; see Fig. 8.
Construct a family $\mathcal{F}$ of $ab+25n$ axis-parallel squares contained
in a rectangle $B\supset R$ as follows. There are two types of squares: (i)
large squares that correspond to the cells of the grid, and (ii) small squares
grouped in clusters of $25$, where each cluster corresponds to a point in $S$.
More precisely, we have $ab$ large squares formed by the cells of the grid,
but only slightly smaller so that they are disjoint. We also have $n$ small
clusters of $25$ small squares each. For each cluster, the middle square can
only be seen by entering the convex hull of the cluster. The clusters are
small enough so that they fit in the narrow corridors left by the big squares.
The center of the central square in a cluster is the _reference_ point of the
cluster; for each point in $p\in S$, the corresponding cluster $C(p)$ has its
reference point at $p$.

The width of the narrow corridors formed by the large squares is set to
$w=1/(10an)$. The side-length of each small square is set to
$s=\frac{w}{100}$. We set
$B=[-\frac{w}{2},a+\frac{w}{2}]\times[-\frac{w}{2},b+\frac{w}{2}]$, where the
$ab$ large squares are defined as
$[i+\frac{w}{2},i+1-\frac{w}{2}]\times[j+\frac{w}{2},j+1-\frac{w}{2}]$ for
$0\leq i\leq a-1$ and $0\leq j\leq b-1$. Between any two adjacent large
squares, there is a narrow rectangular corridor of length $1-w$ and width $w$.
There are also narrow corridors of the same dimensions between the boundary of
$B$ and the adjacent large holes.

The reduction, hence the $\NP$-hardness, follows via the following claim.

_Claim._ For a positive integer $m$, there exists a tour of $S$ of rectilinear
length $m$ if and only if there exists an observation tour of $\mathcal{F}$ of
Euclidean length $m+\delta$, with $-0.4\leq\delta\leq 0.4$.

To verify the claim observe first that the rectilinear distance between any
two (lattice) points in $S$ is an integer. Hence the total rectilinear length
of the shortest tour of the points in $S$ is an integer, say $m$. Observe also
that any tour of the points can be converted into a tour of the family of
squares, and vice versa, by visiting the points in $S$ and the corresponding
clusters in the same order. Moreover, we show below that the lengths of the
two tours are very close to each other. Indeed, on the one hand, by making
only small detours from any given TSP tour for $S$ yields an ORP tour of
$\mathcal{F}$. On the other hand, an ORP tour of $\mathcal{F}$ can be
converted into a TSP tour for $S$ whose length is very close to the original
one. Note the following two properties of sub-paths that visit two consecutive
clusters :

  1. 1.

If the $L_{1}$-distance between two points in $S$ is an integer $d$, $1\leq
d\leq a+b$, then any path between two points from which the central squares of
the corresponding clusters are visible has length at least $d(1-w)$, since any
path has to traverse at least $d$ narrow corridors.

  2. 2.

If the $L_{1}$-distance between two points in $S$ is an integer $d$, then
there is a path of length at most $d+w\leq d(1+w)$ between any two points in
the interiors of the corresponding clusters, since it takes a detour no longer
than $w$ to observe all the squares in a cluster. At most $n$ such small
detours are needed, and each adds at most $w$ to the total length.

It follows that the rectilinear length of the shortest tour of the $n$ points
in $S$ can differ from the (Euclidean) length of the shortest external
watchman tour of $\mathcal{F}$ by at most $2n(a+b)w=2n(a+b)/(10an)\leq 0.4$,
as required. ∎

#### Proof of Theorem 3.

We proceed with the same reduction and a similar claim.

Claim. For a positive integer $m$, there exists a tour of $S$ of rectilinear
length $m$ if and only if there exists an external watchman tour of
$\mathcal{F}$ of Euclidean length $m+\delta$, with $-0.4\leq\delta\leq 0.4$.

It suffices to notice that (i) since $R$ is the smallest axis-aligned
rectangle containing $S$, visiting all the clusters will automatically
guarantee seeing the entire boundary for each of the large squares, and (ii)
it takes a detour no longer than $w$ to see the entire boundary for each
square in a visited cluster. ∎

#### Remarks.

Observe that the integrality requirement for $m$ is crucial. Furthermore, as
in the reduction from [17], no such claim holds if the length of the tour of
the points in $S$ is measured in the $L_{2}$-norm. Observe also that squares
of only two different sizes are used in the reduction. We conjecture that both
ORP and EWRP remain $\NP$-hard even for axis-aligned unit squares.

##  5 Inapproximability results

We deduce the inapproximability of ORP from that of Set Cover. A _set system_
is a pair $(U,\mathcal{S})$, where $U$ is a set and $\S$ is a collection of
subsets of $U$. Given a set system $(U,\mathcal{S})$, the Set Cover problem
asks for the minimum number of sets in $\mathcal{S}$ whose union is $U$. Set
Cover cannot be approximated within a factor of $(1-o(1))\ln n$ unless
$\P=\NP$ [11], where $n=|U|$. Furthermore, for any $c\in(0,1)$, Set Cover
cannot be approximated within a factor of $c\,\ln n$ over instances where
$m\leq O(n^{f(c)})$ for some function $f:(0,1)\to\mathbb{R}$, unless $\P=\NP$
[11, 36]; see also [21, 29, 35, 36].

Given a set system $(U,\mathcal{S})$ with $|U|=n$ and $|\mathcal{S}|=m$, we
construct a family $\mathcal{F}$ of disjoint convex polygons in four stages.
We first construct an arrangement of lines $\mathcal{L}$ in $\mathbb{R}^{2}$,
and then “thicken” the lines into narrow corridors. The family $\mathcal{F}$
will consist of the convex faces of this arrangement and $n+3$ additional
axis-parallel rectangles inserted in the corridors at strategic locations. We
continue with the details; see Fig. 9.

Figure 9: Left: A line arrangement $\mathcal{L}$ constructed in Stage 1; here
$n=7$ and $m=4$. Middle: A slab $N_{i,j}$ and a wedge $W_{i,j}$ for a line
$p_{i}q_{j}\in\mathcal{L}$. Right: A schematic picture of the family
$\mathcal{F}$ (not to scale).

Stage 1. We are given a set system $(U,\mathcal{S})$ with $U=\\{1,\ldots,n\\}$
and $\mathcal{S}=\\{S_{1},\ldots,S_{m}\\}$. Let $M=\max\\{12m,n+1\\}$, and
consider the axis-aligned square $B_{0}=[0,M]^{2}$. Each set $S_{i}$,
$i\in\\{1,\ldots,m\\}$, is represented by the point $p_{i}=(0,i)$ at the left
side of $B_{0}$, and each element $j\in U$ corresponds to the point
$q_{j}=(M,j)$ at the right side of $B_{0}$. Let $\mathcal{L}$ be the set of
lines $p_{i}q_{j}$ such that $j\in S_{i}$.

Stage 2. For each line $p_{i}q_{j}\in\mathcal{L}$, let $N_{i,j}$ be the
$\frac{1}{2}\,M^{-8}$-neighborhood of $\ell$, which is a slab of width
$M^{-8}$. For each line $p_{i}q_{j}\in\mathcal{L}$, we also create a cone
$W_{i,j}$ bounded by the ray $\overrightarrow{p_{i}q_{j}}$ from below and the
ray $\overrightarrow{p_{i}q_{j}^{\prime}}$ from above, where
$q_{j}^{\prime}=(M,j+M^{-4})$ is a point at distance $M^{-4}$ above $q_{j}$,
and in particular $q_{j}^{\prime}\notin N_{i,j}$. Note that $N_{i,j}\cup
W_{i,j}$ is a simply connected region; see Fig. 9(middle).

Consider the axis-aligned rectangle $B_{1}=[-M^{-2},2M]\times[-M,2M]\supset
B_{0}$. Let $\mathcal{F}_{1}$ be the bounded components of
$B_{1}\setminus\bigcup_{i,j}(N_{i,j}\cup W_{i,j})$, that is, we create a
convex polygon for each bounded face of the arrangement $\mathcal{L}$ within
$B_{1}$.

Stage 3. Create a family $\mathcal{F}_{2}$ of the following $n+3$ disjoint
axis-aligned rectangles: a small square $Q_{j}$ of side length $M^{-8}$
centered at the midpoint of $q_{j}q_{j}^{\prime}$ for all $j\in U$; two unit
squares, denoted $C_{1}$ and $C_{2}$, resp., centered at $(-1,-1)$ and
$(-1,M+1)$; and a large rectangle $B_{2}=[-M,-M^{-2}-M^{-4}]\times[0,M]$.

Stage 4. Apply the linear transformation $T:\mathbb{R}^{2}\to\mathbb{R}^{2}$,
$T(x,y)=\left(\frac{M^{2}x}{2},\frac{M^{-1}y}{24}\right)$, and let
$\mathcal{F}=\\{T(C):C\in\mathcal{F}_{1}\cup\mathcal{F}_{2}\\}$.

######  Lemma 7.

For an instance $(U,\mathcal{S})$ of Set Cover with $|U|=n$ and
$|\mathcal{S}|=m$, let $\mathcal{F}$ be the family of disjoint convex polygons
constructed above.

  1. 1.

There is a polynomial $f(m,n)$ such that the total number of vertices of the
polygons in $\mathcal{F}$ is at most $f(m,n)$, each vertex has rational
coordinates where both numerators and denominators are bounded by $f(m,n)$.

  2. 2.

For every integer $k$, $1\leq k\leq m$, the union of $k$ sets in $\mathcal{S}$
covers $U$ if and only if $\mathcal{F}$ admits an observation tour of length
at most $k+\frac{1}{2}$.

###### Proof.

(1) There are at most $mn$ lines in the arrangement $\mathcal{L}$ in Stage 1,
each line can be written in the form $ax+by=c$ with integer coefficients in
the range $[-M,M]$. Each line $p_{i}q_{j}\in\mathcal{L}$ corresponds to a
narrow corridor $N_{i,j}\cup W_{i,j}$ bounded by three lines. The vertices of
the polygons in $\mathcal{F}_{1}$ are intersection points of boundaries of
such corridors: $O(mn)$ lines yield $O(m^{2}n^{2})$ intersection points, which
all have rational coordinates bounded by a polynomial in $m$ and $n$. The
$n+3$ rectangles in $\mathcal{F}_{2}$ are defined explicitly, and they also
have rational coordinates bounded by polynomials in $m$ and $n$. Finally, the
linear transformation in Stage 4 maintains these properties.

(2a) Assume that $k$ sets in $\mathcal{S}$ jointly cover $U$, that is,
$\bigcup_{t=1}^{k}S_{i_{t}}=U$ for some $i_{1},\ldots,i_{k}\in\\{1,\ldots
m\\}$. We construct an observation tour for $\mathcal{F}$. We describe the
tour in terms of the polygons before Stage 4, since a linear transformation
maintains visibility (but distorts distances). Let the initial tour
$\gamma_{0}$ traverse the left side of the rectangle $B_{1}$ twice. The upper-
left and lower-left corners of $B_{1}$ see the squares $C_{1}$ and $C_{2}$,
and every point in $\gamma_{0}$ can see $B_{2}$. The tour $\gamma_{0}$
intersects every line $p_{i}q_{j}\in\mathcal{L}$. The point $\gamma_{0}\cap
p_{i}q_{j}$ can see all convex bodies in $\mathcal{F}_{1}$ whose boundaries
touch the slab $N_{i,j}$. Since the upper arc of every polygon in
$\mathcal{F}_{1}$, other than the polygon containing the top side of $B_{1}$,
is formed by the bottom sides of the slabs $N_{i,j}$, and so $\gamma_{0}$ can
see every polygon in $\mathcal{F}_{1}$.

We expand $\gamma_{0}$ to a tour of $\mathcal{F}_{1}\cup\mathcal{F}_{2}$ as
follows: For $t=1,\ldots,k$, choose an arbitrary point $q_{j_{t}}\in
S_{i_{t}}$, and add a loop from the point $p_{i_{t}}q_{j_{t}}\cap\gamma_{0}$
to the point $p_{i_{t}}$ in the corridor $N(p_{i_{t}}q_{j_{t}})$. The point
$p_{i_{t}}$ can see the small squares representing all $j\in S_{i_{t}}$. Since
$\bigcup_{t=1}^{k}S_{i_{t}}=U$, every small square in $\mathcal{F}_{2}$ is
visible from some point in the tour. After the linear transformation in Stage
4, we obtain an observation tour $\gamma$ for $\mathcal{F}$. We bound the
length of $\gamma$ using the $L_{1}$-norm of its edges. The linear
transformation in Stage 4 compresses the $y$-extents of each edge, so the
$L_{1}$ norm is dominated by the $x$-extents: The $x$-extent of an edge
between the left side of $B_{1}$ and $p_{i}$ is exactly $M^{-2}$, thus the sum
of $x$-extents is $2kM^{-2}$. Accounting for the $y$-extents of these $2k$
edges and $\gamma_{0}$, and applying the linear transformation in Stage 4, we
obtain $|\gamma|\leq k+\frac{1}{2}$, as required.

(2b) Now assume that $\mathcal{F}$ admits an observation tour $\gamma$ with
$|\gamma|\leq k+\frac{1}{2}$. We analyze the construction before Stage 4,
hence the sum of $x$-extents of all edges of the tour is at most
$(2k+1)M^{-2}$. The observation tour intersects the visibility region
$V(Q_{j})$ for all $j\in U$. A square $Q_{j}$ lies in the corridor
$N_{i,j}\cup W_{i,j}$ iff $j\in S_{i}$, and $Q_{j}$ is only visible from such
corridors. Each line $p_{i}q_{j}\in\mathcal{L}$ is incident to two points on
opposite vertical sides of a square, and so its slope is in the range
$[-1,1]$. By construction, $Q_{j}\subset W_{i,j}$ and the cone $W_{i,j}$ is
convex, consequently $W_{i,j}\subset V(Q_{j})$. However, $Q_{j}$ is above the
slab $N_{i,j}$, every vertical segment between them has length at least
$\frac{1}{3}\,M^{-4}$, and so the $x$-coordinate of the leftmost point in
$V(Q_{j})\cap N_{i,j}$ is at least $-M\cdot
M^{-8}/(\frac{1}{3}\,M^{-4})=-3\,M^{-3}$. Overall, the $x$-coordinate of the
leftmost point in $V(Q_{j})$ is at least $-3\,M^{-3}$.

Note that the visibility region $V(C_{1})$ is disjoint from $V(Q_{j})$ for all
$j\in U$. Since $|\gamma|\leq(2k+1)M^{-2}<M^{-1}$, $\gamma$ must be contained
in the vertical slab $\\{(x,y)\in\mathbb{R}^{2}:|x|<M^{-1}\\}$. Consequently,
$\gamma$ visits each visibility region $V(Q_{j})$ in the vertical slab
$\\{(x,y)\in\mathbb{R}^{2}:-3\,M^{-3}<x<M^{-1}\\}$.

Let $I$ be the set of indices $i\in\\{1,\ldots,m\\}$ such that $\gamma$ visits
a point $g_{i}\in(N_{i,j}\cup W_{i,j})\cap V(Q_{j})$ for some $j\in U$. Since
$\gamma$ is an observation tour, we have $U=\cup_{i\in I}S_{i}$. It remains to
show that $|I|\leq k$.

The tour $\gamma$ determines a cyclic order on the points $G=\\{g_{i}:i\in
I\\}$. We claim that the $x$-extent of the arc of $\gamma$ between two
consecutive points in $G$ is at least $2M^{-2}-6M^{-3}$. To prove the claim,
note that every point $p_{i}=(0,2i)$ has integer coordinates, and the slope of
every line $p_{i}q_{j}\in\mathcal{L}$ is in the range $[-1,1]$. This implies
that if two lines in $\mathcal{L}$ cross in the slab
$\\{(x,y)\in\mathbb{R}^{2}:|x|<M^{-1}\\}$, then they cross at $p_{i}$ for some
$i\in U$. Consequently, if visibility corridors, say $N_{i,j}\cup W_{i,j}$ and
$N_{i^{\prime},j^{\prime}}\cup W_{i^{\prime},j^{\prime}}$ intersect, then the
intersection is in a $M^{-8}$-neighborhood of $p_{i}$ for some $i\in U$. It
follows that the arc of $\gamma$ between any two points in $G$ must reach the
line $x=-M^{-2}$ on the left or the line $x=1$ on the right. In both cases,
its arclength is at least $2M^{-2}-6M^{-3}$, as claimed. We can bound the
length of $\gamma$ by the summation of the arcs between consecutive points in
$G$:

$|\gamma|\geq|I|(2M^{-2}-6M^{-3})\geq(2\,|I|)M^{-2}-6mM^{-3}\geq\left(2\,|I|-\frac{1}{2}\right)M^{-2}.$

In combination with $|\gamma|\leq(2k+1)M^{-2}$ and $M\geq 12m$, we obtain that
$|I|\leq k+\frac{3}{4}$. As both $k$ and $|I|$ are integers, $|I|\leq k$
follows. ∎

#### Proof of Theorem 4.

As noted above [11], there exists a constant $\kappa>0$ such that Set Cover
cannot be approximated within a factor of $\kappa\log n$ on instances
$(U,\mathcal{S})$ with $n=|U|$, $m=|\mathcal{S}|$, and $m\leq O(n^{\alpha})$
for a constant $\alpha>0$ unless $\P=\NP$. By Lemma 7, for every such instance
$(U,\mathcal{S})$ of Set Cover, there is a family $\mathcal{F}$ of $N$
disjoint convex polygons in the plane such that (i) for every $k\leq n$, there
is a set cover of size $k$ iff $\mathcal{F}$ admits a observation route of
length at most $k+\frac{1}{2}$, and (ii) $N\leq{mn\choose 2}+n+3\leq
m^{2}n^{2}=O(n^{2\alpha+2})$.

Suppose that for $\delta=\kappa(2\alpha+2)^{-1}>0$, there exists a polynomial-
time $(\delta\log N)$-factor approximation algorithm for ORP with $N$ convex
bodies. Since $\delta\log N\leq\delta(2\alpha+2)\log n=\kappa\log n$, this
yields a $(\kappa\log n)$-approximation for Set Cover, which is a
contradiction unless $\P=\NP$. ∎

##  6 External watchman tours for a convex polygon

Given a polygon, the External Watchman Route problem (EWRP) is that of finding
a shortest route such that each point in the exterior of the polygon is
visible from some point along the route. For a convex polygon, this
requirement is tantamount to requiring that each point on the boundary of the
polygon is visible from some point along the route.

Let $P$ be a convex polygon. Ntafos and Gewali [39] distinguished between two
types of external watchman tours: those that wrap around the perimeter and
those that do not. They also showed that the second type of route can be
obtained by doubling a simple open curve that wraps around a part of $P$’s
boundary and is extended at both ends until the vision encompasses the entire
boundary of $P$; see Fig. 10 for an example. They referred to the second type
as “a $2$-leg watchman route”, see [39].

Figure 10: The two types of external watchman tours.

#### Proof of Theorem 5.

Let $P$ be a convex pentagon whose angles listed in clockwise order from the
top are $120^{\circ}$, $120^{\circ}$, $90^{\circ}$, $90^{\circ}$,
$120^{\circ}$; refer to Fig 11. Its horizontal base has length $2$ and each of
its vertical sides is of length $\varepsilon$, for a small $\varepsilon>0$.
Note that the length of each slanted top side is $a=2/\sqrt{3}$. Observe that
all angles are at least $90^{\circ}$. By slightly shortening the base to
$2(1-\varepsilon^{2})$ the pentagon becomes one with all angles obtuse, say
$P^{\prime}$, whose angles are $120^{\circ}$, $(120-\delta)^{\circ}$,
$(90+\delta)^{\circ}$, $(90+\delta)^{\circ}$, $(120-\delta)^{\circ}$, for some
small $\delta>0$. Its side lengths (listed in the same order) are $a$,
$\varepsilon(1+\varepsilon^{2})^{1/2}$, $2(1-\varepsilon^{2})$,
$\varepsilon(1+\varepsilon^{2})^{1/2}$, $a$. Thus

${\rm
per}(P^{\prime})=2(a+(1-\varepsilon^{2})+\varepsilon(1+\varepsilon^{2})^{1/2})>2(1+a-\varepsilon).$

Figure 11: Left: a pentagon with all angles obtuse can be obtained by slightly
perturbing this one. Right: a second type of watchman route can be obtained by
doubling the red $3$-chain polygonal curve; its two legs are perpendicular to
the extensions of the two top sides. The figure is not to scale.

Observe that the red curve in the figure is a $3$-polygonal chain that makes a
valid watchman path for $P^{\prime}$. Its length is $<2(1+\varepsilon)$ and
thus doubling it yields an external watchman route of length
$<4(1+\varepsilon)$. It remains to show that
$4(1+\varepsilon)<2(1+a-\varepsilon)$ or
$\varepsilon<(a-1)/3=\frac{2-\sqrt{3}}{3\sqrt{3}}$, which clearly holds for
small $\varepsilon>0$. Note that the ratio between the length of the double
red curve and the perimeter is in fact smaller than some absolute constant
$<1$, e.g., $0.93<1$ in the range $\varepsilon\leq 0.001$.

Alternatively, by cutting two small right-angled isosceles triangles, one from
each side of the base of the pentagon one gets a convex heptagon all whose
angles are at least $120^{\circ}$. A similar calculation as above shows that
this heptagon provides yet another counterexample in which all angles are even
larger, here at least $120^{\circ}$.

By slightly ’shaving’ the pentagon in a repeated manner, one can increase the
number of vertices while maintaining all angles obtuse and thereby obtain
counterexamples to Conjecture 1 in [2] for every $n\geq 5$. Note, however,
that since every triangle or convex quadrilateral has at least one nonobtuse
angle, the range for $n$ in Theorem 5 cannot be improved. ∎

##  7 Problem comparison

In this section we compare the optimal solutions to the three problems (ORP,
EWRP, and TSPN) on various instances. While such solutions can differ
substantially, they can be also close to each other in certain natural
scenarios (as in Theorem 6). As a result, we get a better understanding of
these problems.

######  Observation 1.

Let $\mathcal{F}_{1}\subseteq\mathcal{F}_{2}$ be two families of convex
bodies. Then

  1. 1.

$\textsf{OPT}_{\textsf{TSPN}}(\mathcal{F}_{1})\leq\textsf{OPT}_{\textsf{TSPN}}(\mathcal{F}_{2})$

  2. 2.

$\textsf{OPT}_{\textsf{ORP}}(\mathcal{F}_{1})\leq\textsf{OPT}_{\textsf{ORP}}(\mathcal{F}_{2})$

  3. 3.

$\textsf{OPT}_{\textsf{EWRP}}(\mathcal{F}_{1})\leq\textsf{OPT}_{\textsf{EWRP}}(\mathcal{F}_{2})$

We start by observing a key difference between the range of optimal solutions
for these problems. Specifically, we have the following lower bound on the
length of an external watchman route.

######  Lemma 8.

Let $C$ be a convex body and $W$ be an external watchman route for $C$. Then
${\rm len}(W)>0$. Similarly, let $\mathcal{F}$ be a family of disjoint convex
bodies. Then $\textsf{OPT}_{\textsf{EWRP}}(\mathcal{F})>0$.

###### Proof.

Assume that the boundary $\partial C$ is visible from a single point $o$. Take
a ray from $o$ that goes through the interior of $C$ and intersects $\partial
C$ at $p$ and $q$, respectively. Then $q$ is not visible from $o$, a
contradiction, and the first part in the lemma follows. For the second part,
let $C$ denote an arbitrary element of $\mathcal{F}$. By Observation 1,
$\textsf{OPT}_{\textsf{EWRP}}(\mathcal{F})\geq\textsf{OPT}_{\textsf{EWRP}}(\\{C\\})>0$,
as claimed. ∎

We next confirm the intuition “observing is easy, traveling is expensive”.

######  Lemma 9.

There exist families $\mathcal{F}$ of $n$ congruent disks for which
$\textsf{OPT}_{\textsf{EWRP}}(\mathcal{F})\ll\textsf{OPT}_{\textsf{TSPN}}(\mathcal{F})$.
In particular $\textsf{OPT}_{\textsf{EWRP}}(\mathcal{F})=\Theta(1)$ and
$\textsf{OPT}_{\textsf{TSPN}}(\mathcal{F})=\Theta(\sqrt{n})$.

###### Proof.

Assume that $n$ is a perfect square. Place a disk of radius $\varepsilon>0$
centered at each point of the integer lattice $[1,\sqrt{n}]^{2}$. Scale down
the construction so that it fits inside the unit square $[0,1]^{2}$. If the
radius is sufficiently small, there is a watchman route for $\mathcal{F}$ of
length $\Theta(1)$ that goes around and close to the perimeter of ${\rm
conv}(\mathcal{F})$; for a similar setup recall the classical orchard
visibility problem due to Pólya [43]. On the other hand, the length of the
shortest tour visiting each disk is clearly $\Theta(\sqrt{n})$ (recall also
Few’s result [22]). ∎

On the other hand, when disks are densely packed, one expects that the length
of an optimal TSPN tour approximates well the length of an optimal watchman
tour. Indeed, the intuition is that one cannot see too far in a densely packed
forest of congruent trees and in order to see each tree one essentially needs
to visit the entire forest. Moreover, we show that in this scenario the length
of a shortest ORP tour, EWRP tour, and TSPN tour are roughly the same, namely
within constant factors from each other. We recall the following result of
Dumitrescu and Jiang [15] confirming a conjecture by Mitchell. (It is likely
that the result holds for a much smaller radius threshold, possibly $<100$.)

######  Theorem 7.

[15] Any dense (circular) forest with congruent trees (of unit diameter) that
is deep enough has a hidden point.

Using Theorem 7 on one hand and Few’s technique [22] for traversing points in
a square, layer by layer, on the other hand, we can prove that the optimal
solutions for the three problems are roughly the same in this setting.

#### Proof of Theorem 6.

(i) Recall that $\mathcal{F}$ is a maximal packing of unit disks in a large
square $S$. Observe that
$\textsf{OPT}_{\textsf{ORP}}(\mathcal{F})\leq\textsf{OPT}_{\textsf{EWRP}}(\mathcal{F})$
(by problem definition). We start with the lower bounds. Let $A=10^{109}$ and
$s$ denote the side length of $S$. We may assume without loss of generality
that $n$ and $s$ are large enough, in particular that $s$ is a multiple of
$A$. Thus $S$ can be partitioned into $s^{2}/A^{2}$ subsquares of side $A$.
Since $\mathcal{F}$ is a maximal packing we have $n=\Theta(s^{2})$. Let $T$ be
an observation tour for $\mathcal{F}$. Since each of the $s^{2}/A^{2}$
subsquares of side $A$ has a hidden point, $T$ must visit every subsquare.
Moreover, this implies that ${\rm
len}(T)=\Omega(s^{2}/A^{2})-O(s)=\Omega(s^{2}/A^{2})=\Omega(n)$. By the
inequality in the beginning, it follows that
$\textsf{OPT}_{\textsf{EWRP}}(\mathcal{F})\geq\textsf{OPT}_{\textsf{ORP}}(\mathcal{F})=\Omega(n)$.

Next we show that $\textsf{OPT}_{\textsf{TSPN}}(\mathcal{F})=\Omega(n)$. Let
$T$ be a TSPN tour for $\mathcal{F}$. A standard disk packing argument (see
[16, Prop. 1] for details) yields ${\rm len}(T)\geq\pi(n-4)/4$, whence
$\textsf{OPT}_{\textsf{TSPN}}(\mathcal{F})=\Omega(n)$, as claimed.

To prove the upper bounds, we first consider EWRP. Subdivide $S$ into
horizontal strips (rectangles) $s\times 4$ and traverse the strips in a zig-
zag manner, say, from top to bottom. Finally return to the start position by
following the boundary $\partial S$. In every strip, move from left to right
or from right to left and circle around the boundary of each disk in
increasing (resp., decreasing) order of the $x$-coordinates of their centers.
Since $\mathcal{F}$ is a maximal packing, each disk-to-disk move is bounded
from above by $O(1)$ in length and thus the total length is $O(n)$, whence
$\textsf{OPT}_{\textsf{ORP}}(\mathcal{F})\leq\textsf{OPT}_{\textsf{EWRP}}(\mathcal{F})=O(n)$.
Following the same (strip visitation) algorithm while visiting each disk
instead of circling around it, yields
$\textsf{OPT}_{\textsf{TSPN}}(\mathcal{F})=O(n)$, as claimed.

(ii) The stated inequalities have been established when proving Theorems 2 and
3. ∎

##  8 Concluding remarks

We conclude with a few open problems regarding the remaining gaps and the
quality of approximation.

  1. 1.

Is there a constant-ratio approximation algorithm for the shortest observation
tour problem for families of disjoint axis-aligned unit squares (or unit
disks, or translates of a convex polygon)?

  2. 2.

What approximations can be computed for the shortest observation tour for
families of disjoint convex polygons?

  3. 3.

Is there a constant-ratio approximation algorithm for the shortest external
watchman route for families of disjoint axis-aligned unit squares (or unit
disks or translates of a convex polygons)?

  4. 4.

What approximations can be computed for the shortest external watchman route
for families of disjoint convex polygons? Is the problem $\APX$-hard?

## References

  * [1] Mikkel Abrahamsen, Anna Adamaszek, and Tillmann Miltzow.  The art gallery problem is $\exists\mathbb{R}$-complete.  J. ACM, 69(1):4:1–4:70, 2022.  doi:10.1145/3486220.
  * [2] Rafa Absar and Sue Whitesides.  On computing shortest external watchman routes for convex polygons.  In Proceedings of the 18th Annual Canadian Conference on Computational Geometry (CCCG), Kingston, ON, 2006.  URL: http://www.cs.queensu.ca/cccg/papers/cccg16.pdf.
  * [3] Esther M. Arkin and Refael Hassin.  Approximation algorithms for the geometric covering salesman problem.  Discret. Appl. Math., 55(3):197–218, 1994.  doi:10.1016/0166-218X(94)90008-6.
  * [4] Sanjeev Arora.  Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems.  J. ACM, 45(5):753–782, 1998.  doi:10.1145/290179.290180.
  * [5] Édouard Bonnet and Tillmann Miltzow.  Parameterized hardness of art gallery problems.  ACM Trans. Algorithms, 16(4):42:1–42:23, 2020.  doi:10.1145/3398684.
  * [6] Svante Carlsson, Håkan Jonsson, and Bengt J. Nilsson.  Finding the shortest watchman route in a simple polygon.  Discret. Comput. Geom., 22(3):377–402, 1999.  doi:10.1007/PL00009467.
  * [7] Wei-pang Chin and Simeon C. Ntafos.  Optimum watchman routes.  In Proc. 2nd ACM Symposium on Computational Geometry (SoCG), pages 24–33, 1986.  doi:10.1145/10515.10518.
  * [8] Wei-pang Chin and Simeon C. Ntafos.  Optimum watchman routes.  Inf. Process. Lett., 28(1):39–44, 1988.  doi:10.1016/0020-0190(88)90141-X.
  * [9] Wei-pang Chin and Simeon C. Ntafos.  Shortest watchman routes in simple polygons.  Discret. Comput. Geom., 6:9–31, 1991.  doi:10.1007/BF02574671.
  * [10] Mark de Berg, Joachim Gudmundsson, Matthew J. Katz, Christos Levcopoulos, Mark H. Overmars, and A. Frank van der Stappen.  TSP with neighborhoods of varying size.  J. Algorithms, 57(1):22–36, 2005.  doi:10.1016/j.jalgor.2005.01.010.
  * [11] Irit Dinur and David Steurer.  Analytical approach to parallel repetition.  In Proc. 46th ACM Symposium on Theory of Computing (STOC), pages 624–633, 2014.  doi:10.1145/2591796.2591884.
  * [12] Moshe Dror, Alon Efrat, Anna Lubiw, and Joseph S. B. Mitchell.  Touring a sequence of polygons.  In Proc. 35th ACM Symposium on Theory of Computing (STOC), pages 473–482, 2003.  doi:10.1145/780542.780612.
  * [13] Moshe Dror and James B. Orlin.  Combinatorial optimization with explicit delineation of the ground set by a collection of subsets.  SIAM J. Discret. Math., 21(4):1019–1034, 2008.  doi:10.1137/050636589.
  * [14] Adrian Dumitrescu, Annette Ebbers-Baumann, Ansgar Grüne, Rolf Klein, and Günter Rote.  On the geometric dilation of closed curves, graphs, and point sets.  Comput. Geom., 36(1):16–38, 2007.  doi:10.1016/j.comgeo.2005.07.004.
  * [15] Adrian Dumitrescu and Minghui Jiang.  The forest hiding problem.  Discret. Comput. Geom., 45(3):529–552, 2011.  doi:10.1007/s00454-010-9261-4.
  * [16] Adrian Dumitrescu and Joseph S. B. Mitchell.  Approximation algorithms for TSP with neighborhoods in the plane.  J. Algorithms, 48(1):135–159, 2003.  doi:10.1016/S0196-6774(03)00047-6.
  * [17] Adrian Dumitrescu and Csaba D. Tóth.  Watchman tours for polygons with holes.  Comput. Geom., 45(7):326–333, 2012.  doi:10.1016/j.comgeo.2012.02.001.
  * [18] Annette Ebbers-Baumann, Ansgar Grüne, and Rolf Klein.  Geometric dilation of closed planar curves: New lower bounds.  Comput. Geom., 37(3):188–208, 2007.  doi:10.1016/j.comgeo.2004.12.009.
  * [19] Stephan J. Eidenbenz, Christoph Stamm, and Peter Widmayer.  Inapproximability results for guarding polygons and terrains.  Algorithmica, 31(1):79–113, 2001.  doi:10.1007/s00453-001-0040-8.
  * [20] Khaled M. Elbassioni, Aleksei V. Fishkin, and René Sitters.  Approximation algorithms for the Euclidean traveling salesman problem with discrete and continuous neighborhoods.  Int. J. Comput. Geom. Appl., 19(2):173–193, 2009.  doi:10.1142/S0218195909002897.
  * [21] Uriel Feige.  A threshold of ln _n_ for approximating set cover.  J. ACM, 45(4):634–652, 1998.  doi:10.1145/285055.285059.
  * [22] Leonard Few.  The shortest path and shortest road through $n$ points.  Mathematika, 2:141–144, 1955.  doi:10.1112/S0025579300000784.
  * [23] Michael R. Garey, Ronald L. Graham, and David S. Johnson.  Some NP-complete geometric problems.  In Proc. 8th ACM Symposium on Theory of Computing (STOC), pages 10–22, 1976.  doi:10.1145/800113.803626.
  * [24] Michael R. Garey and David S. Johnson.  Computers and Intractability: A Guide to the Theory of $\NP$-Completeness.  W. H. Freeman and Company, New York, NY, 1979.
  * [25] Laxmi P. Gewali and Simeon C. Ntafos.  Watchman routes in the presence of a pair of convex polygons.  Journal of Information Sciences, 105(1-4):123–149, 1998.  doi:10.1016/S0020-0255(97)10033-0.
  * [26] Joachim Gudmundsson and Christos Levcopoulos.  A fast approximation algorithm for TSP with neighborhoods.  Nord. J. Comput., 6(4):469, 1999.
  * [27] David G. Kirkpatrick.  An $o(\lg\lg opt)$-approximation algorithm for multi-guarding galleries.  Discret. Comput. Geom., 53(2):327–343, 2015.  doi:10.1007/s00454-014-9656-8.
  * [28] Christos Levcopoulos and Andrzej Lingas.  Bounds on the length of convex partitions of polygons.  In Proc. 4th Foundations of Software Technology and Theoretical Computer Science (FSTTCS), volume 181 of LNCS, pages 279–295. Springer, 1984.  doi:10.1007/3-540-13883-8\\_78.
  * [29] Carsten Lund and Mihalis Yannakakis.  On the hardness of approximating minimization problems.  J. ACM, 41(5):960–981, 1994.  doi:10.1145/185675.306789.
  * [30] Cristian S. Mata and Joseph S. B. Mitchell.  Approximation algorithms for geometric tour and network design problems (extended abstract).  In Proc. 11th ACM Symposium on Computational Geometry (SoCG), pages 360–369, 1995.  doi:10.1145/220279.220318.
  * [31] Joseph S. B. Mitchell.  Guillotine subdivisions approximate polygonal subdivisions: A simple polynomial-time approximation scheme for geometric TSP, $k$-MST, and related problems.  SIAM J. Comput., 28(4):1298–1309, 1999.  doi:10.1137/S0097539796309764.
  * [32] Joseph S. B. Mitchell.  Geometric shortest paths and network optimization.  In Jörg-Rüdiger Sack and Jorge Urrutia, editors, Handbook of Computational Geometry, pages 633–701. North Holland / Elsevier, 2000.  doi:10.1016/b978-044482537-7/50016-4.
  * [33] Joseph S. B. Mitchell.  Approximating watchman routes.  In Proc. 24th ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 844–855, 2013.  doi:10.1137/1.9781611973105.60.
  * [34] Joseph S. B. Mitchell.  Shortest paths and networks.  In J.E. Goodman, J. O’Rourke, and C.D. Tóth, editors, Handbook of Discrete and Computational Geometry, chapter 31, pages 811–848. CRC Press, 3rd edition, 2017.
  * [35] Dana Moshkovitz.  The projection games conjecture and the NP-hardness of $\ln n$-approximating set-cover.  Theory Comput., 11:221–235, 2015.  doi:10.4086/toc.2015.v011a007.
  * [36] Jelani Nelson.  A note on set cover inapproximability independent of universe size.  Electron. Colloquium Comput. Complex., TR07-105, 2007.  URL: https://eccc.weizmann.ac.il/eccc-reports/2007/TR07-105/index.html, arXiv:TR07-105.
  * [37] Bengt J. Nilsson and Paweł Żyliński.  How to keep an eye on small things.  International Journal of Computational Geometry & Applications, 30(02):97–120, 2020.  doi:10.1142/S0218195920500053.
  * [38] Simeon C. Ntafos.  Watchman routes under limited visibility.  Comput. Geom., 1:149–170, 1992.  doi:10.1016/0925-7721(92)90014-J.
  * [39] Simeon C. Ntafos and Laxmi P. Gewali.  External watchman routes.  Vis. Comput., 10(8):474–483, 1994.  doi:10.1007/BF01910637.
  * [40] J. O’Rourke.  Visibility.  In J.E. Goodman, J. O’Rourke, and C.D. Tóth, editors, Handbook of Discrete and Computational Geometry, chapter 33, pages 875–896. CRC Press, 3rd edition, 2017.
  * [41] Joeseph O’Rourke and Subhash Suri an Csaba D. Tóth.  Polygons.  In J.E. Goodman, J. O’Rourke, and C.D. Tóth, editors, Handbook of Discrete and Computational Geometry, chapter 30, pages 787–810. CRC Press, 3rd edition, 2017.
  * [42] Christos H. Papadimitriou.  The Euclidean traveling salesman problem is NP-complete.  Theor. Comput. Sci., 4(3):237–244, 1977.  doi:10.1016/0304-3975(77)90012-3.
  * [43] George Pólya.  Zahlentheoretisches und Wahrscheinlichkeitstheoretisches über die Sichweite im Walde.  Arch. Math. Phys. Series 2, 27:135–142, 1918.
  * [44] Shmuel Safra and Oded Schwartz.  On the complexity of approximating tsp with neighborhoods and related problems.  Comput. Complex., 14(4):281–307, 2006.  doi:10.1007/s00037-005-0200-3.
  * [45] Paul R. Scott and Poh Wah Awyong.  Inequalities for convex sets.  Journal of Inequalities in Pure and Applied Mathematics, 1:article 6, 2000.
  * [46] Xuehou Tan.  Fast computation of shortest watchman routes in simple polygons.  Inf. Process. Lett., 77(1):27–33, 2001.  doi:10.1016/S0020-0190(00)00146-0.
  * [47] Xuehou Tan.  A linear-time 2-approximation algorithm for the watchman route problem for simple polygons.  Theor. Comput. Sci., 384(1):92–103, 2007.  doi:10.1016/j.tcs.2007.05.021.
  * [48] Xuehou Tan, Tomio Hirata, and Yasuyoshi Inagaki.  Corrigendum to ”An incremental algorithm for constructing shortest watchman routes”.  Int. J. Comput. Geom. Appl., 9(3):319–323, 1999.  doi:10.1142/S0218195999000212.
  * [49] Jorge Urrutia.  Art gallery and illumination problems.  In Jörg-Rüdiger Sack and Jorge Urrutia, editors, Handbook of Computational Geometry, pages 973–1027. North Holland / Elsevier, 2000.  doi:10.1016/b978-044482537-7/50023-1.


# Fragile antiferromagnetism in the heavy-fermion compound YbBiPt

B. G. Ueland  Ames Laboratory, U.S. DOE, Iowa State University, Ames, Iowa
50011, USA  Department of Physics and Astronomy, Iowa State University, Ames,
Iowa 50011, USA  A. Kreyssig  Ames Laboratory, U.S. DOE, Iowa State
University, Ames, Iowa 50011, USA  Department of Physics and Astronomy, Iowa
State University, Ames, Iowa 50011, USA  K. Prokeš  Helmholtz-Zentrum Berlin
für Materialien und Energie, Hahn-Meitner-Platz 1, 14109 Berlin, Germany  J.
W. Lynn  NIST Center for Neutron Research, National Institute of Standards and
Technology, Gaithersburg, Maryland 20899, USA  L. W. Harriger  NIST Center for
Neutron Research, National Institute of Standards and Technology,
Gaithersburg, Maryland 20899, USA  D. K. Pratt  NIST Center for Neutron
Research, National Institute of Standards and Technology, Gaithersburg,
Maryland 20899, USA  D. K. Singh  NIST Center for Neutron Research, National
Institute of Standards and Technology, Gaithersburg, Maryland 20899, USA
Department of Materials Science and Engineering, University of Maryland,
College Park, MD 20742, USA  T. W. Heitmann  The Missouri Research Reactor,
University of Missouri, Columbia, Missouri 65211, USA  S. Sauerbrei  Ames
Laboratory, U.S. DOE, Iowa State University, Ames, Iowa 50011, USA  Department
of Physics and Astronomy, Iowa State University, Ames, Iowa 50011, USA  S. M.
Saunders  Ames Laboratory, U.S. DOE, Iowa State University, Ames, Iowa 50011,
USA  Department of Physics and Astronomy, Iowa State University, Ames, Iowa
50011, USA  E. D. Mun  Ames Laboratory, U.S. DOE, Iowa State University, Ames,
Iowa 50011, USA  Department of Physics and Astronomy, Iowa State University,
Ames, Iowa 50011, USA  S. L. Bud’ko  Ames Laboratory, U.S. DOE, Iowa State
University, Ames, Iowa 50011, USA  Department of Physics and Astronomy, Iowa
State University, Ames, Iowa 50011, USA  R. J. McQueeney  Ames Laboratory,
U.S. DOE, Iowa State University, Ames, Iowa 50011, USA  Department of Physics
and Astronomy, Iowa State University, Ames, Iowa 50011, USA  P. C. Canfield
Ames Laboratory, U.S. DOE, Iowa State University, Ames, Iowa 50011, USA
Department of Physics and Astronomy, Iowa State University, Ames, Iowa 50011,
USA  A. I. Goldman  Ames Laboratory, U.S. DOE, Iowa State University, Ames,
Iowa 50011, USA  Department of Physics and Astronomy, Iowa State University,
Ames, Iowa 50011, USA

###### Abstract

We report results from neutron scattering experiments on single crystals of
YbBiPt that demonstrate antiferromagnetic order characterized by a propagation
vector, $\bm{\tau}_{\rm{AFM}}$ = ($\frac{1}{2}\frac{1}{2}\frac{1}{2}$), and
ordered moments that align along the [1 1 1] direction of the cubic unit cell.
We describe the scattering in terms of a two-Gaussian peak fit, which consists
of a narrower component that appears below $T_{\rm{N}}~{}\approx~{}0.4$ K and
corresponds to a magnetic correlation length of $\xi_{\rm{n}}\approx$ 80
$\rm{\AA}$, and a broad component that persists up to $T^{*}\approx$ 0.7 K and
corresponds to antiferromagnetic correlations extending over
$\xi_{\rm{b}}\approx$ 20 $\rm{\AA}$. Our results illustrate the fragile
magnetic order present in YbBiPt and provide a path forward for microscopic
investigations of the ground states and fluctuations associated with the
purported quantum critical point in this heavy-fermion compound.

###### pacs:

75.30.Mb, 75.50.Ee, 75.30.Kz, 71.10.Hf

Unusual magnetic behavior may occur in heavy-fermion systems Stewart_1984  in
close proximity to a magnetic quantum critical point (QCP) Stewart_2001 ;
Stockert_2011 ; Si_2010_1  due to the entanglement of conduction electrons and
localized moments and the competition between potential ground states
Senthil_2004 ; Si_2010 . Quantum phase transitions occur at $T$ = 0 K and are
driven by some non-thermal parameter such as magnetic field or pressure
Sachdev_1999 . In strongly-correlated electron systems such as heavy-fermions
compounds, quantum phase transitions may be accompanied by large changes in
the Fermi-surface and can lead to non-Fermi liquid behavior, enhanced quantum
fluctuations, and may result in superconductivity or other novel ground states
Si_2010 ; Coleman_2007 .

Two scenarios are often discussed in the context of heavy-fermions with QCPs
Stockert_2011 : (1) the conventional spin-density-wave (SDW) scenario where
the quasiparticles are formed below the Kondo temperature ($T_{\rm{K}}$) and
survive in the vicinity of the QCP yielding critical fluctuations localized at
small regions of the Fermi-surface Hertz_1976 ; Millis_1993 ; and (2) the
Kondo breakdown scenario Si_2010  where localization of the _f_ electrons at
the QCP breaks the Kondo coupling yielding large changes of the Fermi-surface
accompanied by a magnetic transition. CeCu2Si2 Stockert_2004  and
Ce1-xLaxRu2Si2 Knafo_2009  are cited as examples of materials described by the
conventional SDW scheme, whereas CeCu6-xAux Si_2001  and YbRh2Si2
Friedemann_2009  provide examples relevant to the latter scenario.

Experiments on YbRh2-xIrxSi2 have shown that substituting 6% Ir for Rh
detaches the Kondo-breakdown point from the QCP resulting in an extended
intermediate-field range of non-Fermi liquid (NFL) behavior, characteristic of
a ”spin-liquid”-type ground state Friedemann_2009 . The stoichiometric
compound YbAgGe Budko_2004  also exhibits an extended region of NFL behavior
with applied magnetic field Niklowitz_2006 ; Schmiedeshoff_2011 . However,
accessing the ordered magnetic state close to the QCP and studying the
evolution of the microscopic magnetic correlations in the NFL regime is
complicated by either the requirement of attaining extremely low temperatures
($T_{\rm{N}}~{}\approx~{}0.05$ K) for YbRh2Si2 Ishida_2003 ; Stock_2012 , or
by a complex series of magnetic transitions with applied field for YbAgGe
Schmiedeshoff_2011 . YbBiPt offers an important alternative stoichiometric
system with: (1) the simplicity of a cubic lattice; (2) temperatures and
fields that are low, but readily achievable for scattering measurements close
to the QCP; and (3) a rather simple $H-T$ phase diagram with an extended
region of NFL behavior Canfield_1991 ; Fisk_1991 ; Movshovich_1994 ;
Canfield_1994 ; Mun_2013 ; Robinson_1994 .

YbBiPt belongs to the series of cubic half-Heusler (space group
$F\overline{4}3m$) $R$BiPt compounds (_R_ = rare earth) Robinson_1994 ;
Wosnitza_2006 ; Kreyssig_2011 , with the magnetic Yb ions forming a face-
centered-cubic magnetic sublattice. Its discovery generated strong interest
due to its extraordinary Sommerfield coefficient ($\gamma~{}\approx$ 8
J/mol-K2) and classification as a heavy-fermion compound Canfield_1991 ;
Fisk_1991 ; Movshovich_1994 ; Canfield_1994 . All of its relevant energy
scales including the Kondo temperature ($T_{\rm{K}}\approx$ 1 K) that
describes the magnetic coupling between the localized and itinerant moments,
the Weiss temperature ($\theta_{\rm{W}}\approx$ -2 K) that describes the mean-
field magnetic exchange strength, the Néel temperature for the proposed spin-
density-wave order ($T_{\rm{N}}$ = 0.4 K), and the crystalline electric field
splitting ($\Delta E<$ 1 meV) are small and comparable, suggesting a complex
interplay of competing interactions at low temperature. It has also been
suggested that YbBiPt offers the realization of a topological Kondo insulator
Chadov_2010 .

Much of the recent attention on YbBiPt has focused on the possibility of a
magnetic-field-tuned antiferromagnetic (AFM) QCP occurring at a low critical
magnetic field of $\mu_{0}H_{\rm{c}}$ = 0.4 T Mun_2013 . Thermodynamic and
transport measurements in ambient field suggest that YbBiPt manifests AFM
order below $T_{\rm{N}}$ = 0.4 K. In particular, a clear anomaly is observed
at $T_{\rm{N}}$ in electrical resistance data that is consistent with spin-
density-wave type AFM order that partially gaps the Fermi surface
Canfield_1991 . This feature is strongly suppressed upon the application of a
modest magnetic field ($\mu_{0}H>\mu_{0}H_{\rm{c}}$), and non-Fermi liquid
behavior is found for $\mu_{0}H_{\rm{c}}<H<$ 0.8 T, followed by Fermi-liquid
behavior for $\mu_{0}H>$ 0.8 T Mun_2013 . Although the locations of the field-
induced phase transitions and Fermi-liquid behavior have been mapped out
Mun_2013 , it is not yet clear whether YbBiPt is best described by the
conventional SDW or the Kondo breakdown scenario.

It also is notable that scattering measurements over the past 22 years have
failed to identify magnetic ordering in powder Robinson_1994  or single
crystal samples, leading to uncertainty regarding the true nature of the
proposed AFM transition that is somewhat reminiscent of the ”hidden order”
paradox in URu2Si2 Mydosh_2011 . Furthermore, muon spin-relaxation ($\mu$SR)
measurements have found evidence of spatially inhomogeneous and disordered
magnetism in powder samples Amato_1992  which suggests that any magnetic order
in YbBiPt is likely quite fragile. Clarifying the nature of the transition at
$T$ = 0.4 K in YbBiPt represents a key step towards performing microscopic
investigations of magnetism close to the QCP.

Here, we present results from neutron scattering experiments on single
crystals of YbBiPt that identify and characterize the low temperature AFM
order by the magnetic propagation vector $\bm{\tau}_{\rm{AFM}}$ =
($\frac{1}{2}~{}\frac{1}{2}~{}\frac{1}{2}$) and moments collinear with
$\bm{\tau}_{\rm{AFM}}$. We further show that the observed magnetic scattering
can be modeled by a two-Gaussian peak fit consisting of a narrower Gaussian
component that appears below $T_{\rm{N}}$ with a magnetic correlation length
of $\xi_{\rm{n}}\approx$ 80 $\rm{\AA}$, and a broader Gaussian component that
persists up to $T^{*}\approx$ 0.7 K that is consistent with short-range AFM
correlations occurring over $\xi_{\rm{b}}\approx$ 20 $\rm{\AA}$. We suggest
that the narrower and broad components of the scattering illustrate the
competition among the low-energy magnetic interactions and lend themselves to
a picture of fragile magnetic order occurring at low temperature.

Figure 1: (color online) Contour plots of diffraction data taken for points in
the ($HHL$) plane corresponding to the antiferromagnetic propagation vector
$\bm{\tau}_{\rm{AFM}}$ = ($\frac{1}{2}\frac{1}{2}\frac{1}{2}$). The intensity
of the scattering is indicated by color. (a) Data for the
($\frac{1}{2}\frac{1}{2}\frac{5}{2}$) position for $T$ = 0.1 K and (b) $T$ =
0.75 K, and (c) after subtracting $T$ = 0.1 K data by the $T$ = 0.75 K data.
Panels (d) and (e) show data for the ($\frac{1}{2}\frac{1}{2}\frac{3}{2}$) and
($\frac{1}{2}\frac{1}{2}\frac{1}{2}$) positions, respectively, after
subtracting the $T$ = 0.1 K data by the corresponding $T$ = 0.8 K data. (f)
Diagram of the ($HHL$) reciprocal lattice plane for YbBiPt. Nuclear Bragg
points are indicated by black crosses, and possible magnetic Bragg points are
indicated by circles. Solid circles correspond to measured points, and points
where the intensity of the magnetic scattering is zero are marked with
$\times$’s. Dashed lines indicate the magnetic Brillouin zones. Figure 2:
(color online) Detailed scattering data for
($\frac{1}{2}\frac{1}{2}\frac{3}{2}$). (a) Data from a rocking scan taken at
$T$ = 0.08 K. Blue and red lines show the broad and narrower components of the
two-Gaussian peak fit, respectively, and the shaded red area corresponds to
scattering contributed by the narrower Gaussian peak. Black crosses at the
bottom show scaled data from a rocking scan at the (1 1 1) nuclear Bragg peak,
which is split due to a small misalignment of the two co-aligned crystals. (b)
Data from rocking scans taken at $T$ = 0.45 K (open circles) and 0.75 K
(filled dark gray circles). The blue curve represents a fit to a single
Gaussian peak, while the dark gray line depicts the background. (c)
$Q$-dependence of the scattering at ($\frac{1}{2}\frac{1}{2}\frac{3}{2}$) and
($\frac{1}{2}\frac{1}{2}\frac{5}{2}$) compared to the square of the Yb3+
magnetic form factor (solid line). (d) Energy dependence of the scattering
from constant Q scans at $T$ = 0.08 K for Q =
($\frac{1}{2}\frac{1}{2}\frac{3}{2}$) (upward pointing triangles), and
background scans at two different Q-positions (circles and downward pointing
triangles). Lines represent fits to Gaussian peaks, and the energy resolution
(FWHM) is indicated by the horizontal line. The shaded area corresponds to
elastic magnetic scattering at ($\frac{1}{2}\frac{1}{2}\frac{3}{2}$).
Uncertainties represent one standard deviation.

Single crystals of YbBiPt were grown out of a Bi flux as described previously
Mun_2013  and ranged in mass from several hundred mg to nearly 2 g. Several
samples with total masses of 1 - 3 g and total mosaic spreads of $\approx
1^{\circ}$ FWHM were assembled for neutron scattering experiments using either
one crystal or two co-aligned crystals. Given the strong sensitivity of the
samples to pressure and strain Movshovich_1994 ; Mun_2013 , several methods
and glues [an amorphous fluoropolymer (CYTOP) or dental glue (HBM X60)] were
used to fix the crystals to a Cu sample holder which was then thermally
anchored to the bottom of a dilution refrigerator. For the samples attached
with the fluoropolymer, Cu wire was loosely wrapped around the crystals and
anchored to the sample holder to ensure mechanical stability.

Neutron scattering experiments were performed on the E-4 two-axis
diffractometer at Helmholtz-Zentrum Berlin, and the SPINS cold-neutron and
BT-7 thermal-neutron triple-axis spectrometers Lynn_2012  at the NIST Center
for Neutron Research. Incident neutrons with wavelengths of $\lambda$ = 2.451,
5.504, and 2.359 Å, for E-4, SPINS, and BT-7, respectively, were selected by a
pyrolitic graphite (PG) monochromator, and PG or liquid nitrogen cooled Be
filters were inserted to reduce contamination from higher-order wavelengths. A
40′ or 80′ Söller collimator was used between the monochromator and sample and
a 120′ (E-4 and SPINS) or 80′ (BT-7) radial collimator was placed immediately
after the sample. BT-7 was operated in two-axis mode and both E-4 and BT-7
utilized position sensitive detectors. On SPINS, a PG analyzer horizontally
focused to a single 3He detector was used to select a fixed final neutron
wavelength of $\lambda$ = 5.504 Å. The LAMP and DAVE software packages were
used for data reduction LAMP ; DAVE .

Comprehensive searches for magnetic scattering in the ($H0L$) and ($HHL$)
reciprocal lattice planes were undertaken on E-4 and resulted in the discovery
of additional scattering below $T^{*}\approx$ 0.7 K at half-integer positions
($\frac{h}{2}\frac{h}{2}\frac{l}{2}$) with $h$ and $l$ odd integers and $h\neq
l$. Fig. 1 shows diffraction data from rocking scans taken in the ($HHL$)
plane using the BT-7 spectrometer. Figure 1(a) shows a broad peak (in both the
longitudinal and transverse directions) centered at
($\frac{1}{2}\frac{1}{2}\frac{5}{2}$) for $T$ = 0.1 K, and Fig. 1(b) shows
that the peak is absent for $T$ = 0.75 K. Figure 1(c) shows the same region
after subtracting the $T$ = 0.75 K data from the $T$ = 0.1 K data. Figures
1(d) and (e) show similar plots of $T$ = 0.1 K data after subtracting $T$ =
0.8 K data for the ($\frac{1}{2}\frac{1}{2}\frac{3}{2}$) and
($\frac{1}{2}\frac{1}{2}\frac{1}{2}$) positions, respectively. A broad peak
centered at ($\frac{1}{2}\frac{1}{2}\frac{3}{2}$), similar to the one at
($\frac{1}{2}\frac{1}{2}\frac{5}{2}$), is observed in Fig. 1(d), whereas Fig.
1(e) shows that the peak is absent at the
($\frac{1}{2}\frac{1}{2}\frac{1}{2}$) position. Although not shown, distinct
but broad peaks similar to those in Figs. 1(c) and (d) were identified at the
($\pm\frac{1}{2}\pm\frac{1}{2}\mp\frac{3}{2}$) and
($\pm\frac{3}{2}\pm\frac{3}{2}\pm\frac{1}{2}$) positions, whereas no peaks
were observed at the ($\pm\frac{3}{2}\pm\frac{3}{2}~{}\frac{3}{2}$) positions.
Figure 1(f) shows a diagram which summarizes our observations in the first
quadrant of the ($HHL$) plane. Since the intensity of the magnetic scattering
is proportional to the component of the moment perpendicular to the neutron
momentum transfer, Q, the systematic absence of scattering at the
($\frac{1}{2}\frac{1}{2}\frac{1}{2}$) and
($\pm\frac{3}{2}\pm\frac{3}{2}~{}\frac{3}{2}$) positions indicates that the
ordered moment is aligned along the [1 1 1] direction. Hence, we conclude that
the AFM propagation vector is $\bm{\tau}_{\rm{AFM}}$ =
($\frac{1}{2}\frac{1}{2}\frac{1}{2}$), and that the ordered moments are
collinear with $\bm{\tau}_{\rm{AFM}}$.

To study the magnetic scattering in more detail, we performed measurements on
a co-aligned sample on the SPINS spectrometer as a function of the neutron
energy transfer $E$. Elastic ($E$ = 0) data from rocking scans centered at the
($\frac{1}{2}\frac{1}{2}\frac{3}{2}$) position for $T$ = 0.08 K are shown in
Fig. 2(a), and data for $T$ = 0.45 and 0.75 K are shown in Fig. 2(b). For
comparison, data from a rocking scan through the (1 1 1) nuclear Bragg peak
are shown at the bottom of Fig. 2(a). The magnetic scattering at $T$ = 0.08
and 0.45 K is much broader than the nuclear peak which indicates that a finite
magnetic correlation length exists for the AFM order. For $T$ = 0.75 K the
magnetic peaks are absent. Upon lowering the temperature below $T^{*}$, broad
scattering appears that grows in intensity with decreasing temperature and is
well described by a single Gaussian peak. For temperatures below
$T_{\rm{N}}~{}\approx$ 0.4 K, Fig. 2(a) shows that a single Gaussian peak no
longer adequately describes the observed scattering since additional intensity
with a narrower distribution is evident for $T$ = 0.08 K, and we describe the
scattering data for $T<T_{\rm{N}}$ by a two-Gaussian peak fit that is the sum
of a broad Gaussian component and a concentric narrower Gaussian component.
Since the centers and the FWHM’s of the broad and narrower components of the
two-Gaussian peak fit do not vary significantly with temperature, they were
fixed to the values obtained at $T$ = 0.08 K [$\Delta\theta_{\rm{narrow}}$ =
3.2(9)∘ and $\Delta\theta_{\rm{broad}}$ = 12.5(9)∘]. A constant background
determined at $T$ = 0.75 K has also been used.

Normalizing to the integrated intensity of the (1 1 1) nuclear reflection, and
assuming equally populated magnetic domains and contributions from the full
volume of the sample, we calculate the average magnetic moment at $T$ = 0.08 K
associated with the total measured magnetic scattering at
$\bm{\tau}_{\rm{AFM}}$ to be $\approx~{}0.8~{}\mu_{\rm{B}}$. At this point we
do not attempt to partition the ordered moment between the broad and narrower
components but note that the ratio of their integrated intensities is
approximately 12:1. For the magnetic structure described above, we can also
compare the $Q$-dependence of the scattering at the
($\frac{1}{2}\frac{1}{2}\frac{3}{2}$) and
($\frac{1}{2}\frac{1}{2}\frac{5}{2}$) magnetic Bragg positions with that
expected for the Yb3+ magnetic form factor [see Fig. 2(c)] and find good
agreement. Taken together with the systematic absence of scattering at the
($\frac{1}{2}\frac{1}{2}\frac{1}{2}$) and
($\pm\frac{3}{2}\pm\frac{3}{2}~{}\frac{3}{2}$) positions, these data confirm
the magnetic origin of the half-integer diffraction peaks.

Figure 3: (color online) Temperature dependence of the integrated intensities
of the narrower (left axis) and broad (right axis) components of the two-
Gaussian peak fits to the magnetic scattering at
($\frac{1}{2}~{}\frac{1}{2}~{}\frac{3}{2}$).

We note that the data below $T_{\rm{N}}$ may also be described by a single
Lorentzian-squared peak although the fit does not quite capture all of the
low-temperature intensity at the center of the peak. Further measurements
using significantly larger samples may be required to ultimately determine the
most appropriate fitting function for the magnetic scattering. Nevertheless,
the temperature dependence of the integrated intensities of the components of
the two-Gaussian peak fit are shown in Fig. 3 and suggest that the two-
Gaussian peak fit captures the essential features of the scattering: the
narrower component decreases smoothly with increasing temperature and is
absent above $T_{\rm{N}}$ $\approx$ 0.4 K, consistent with the bulk
thermodynamic and transport measurement results, while the integrated
intensity of the broad component also decreases smoothly with increasing
temperature but persists up to $T^{*}\approx 0.7$ K.

The magnetic correlation lengths associated with the components of the two-
Gaussian peak fit can be derived from the FWHM of the peaks in the rocking
scan data and are $\xi_{\rm{n}}\approx 80$ Å and $\xi_{\rm{b}}\approx 20$ Å
for the narrower and broad components, respectively. The presence of broad
magnetic scattering and finite correlation lengths appears consistent with
previous $\mu$SR measurements on powder samples which concluded that the
ordered moment in YbBiPt is spatially inhomogeneous Amato_1992 . However, the
$\mu$SR measurements were performed on powders raising the possibility of
strain effects Mun_2013 . The present measurements were performed on single
crystals mounted to minimize or eliminate strain effects.

We believe that this unusual magnetic behavior is intrinsic to YbBiPt and does
not arise from chemical or structural inhomogeneities because: (1) The broad
magnetic component has been found for all three sets of measured samples
despite the crystals coming from different growth batches and despite
different mounting methods. (2) All samples measured present resolution
limited nuclear diffraction peak widths in longitudinal and transverse scans.
(3) Resistivity measurements on samples from batches prepared in an identical
manner all exhibit a single sharp transition at $T=0.4$ K. (4) The measured
residual resistivity ratios are on the order of 20:1, and quantum oscillations
have been observed in the thermopower Mun_2013  and magnetoresistance data
Mun_thesis . (5) Previous neutron powder diffraction measurements found no
evidence of chemical disorder in identically grown YbBiPt samples. (6) We made
measurements on two crystals of YbBiPt (selected from the batches used for our
neutron scattering measurements) using high energy (232 keV) x-ray diffraction
to probe the bulk of the crystals and found no second phase coherent with the
YbBiPt chemical lattice. Nevertheless, the apparent onset of short-range
magnetic correlations at $T^{*}$ is surprising since it is well above
$T_{\rm{N}}$ and, to the best of our knowledge, no distinct signature of this
feature has been previously reported. Given the relatively small ordered
moment and the sizable broadening of the magnetic peaks, it is also now clear
why previous neutron powder diffraction measurements failed to detect the
magnetic order Robinson_1994 .

To check whether the scattering at $\bm{\tau}_{\rm{AFM}}$ arises from low-
energy magnetic fluctuations rather than static order we performed constant-Q
energy scans for $T$ = 0.08 K on SPINS at Q =
($\frac{1}{2}~{}\frac{1}{2}~{}\frac{3}{2}$), and at positions well separated
from the AFM Bragg position to capture the incoherent scattering background.
These data are shown in Fig. 2(d), where the shaded area corresponds to the
additional magnetic scattering at the AFM position. The lines in Fig. 2(d)
represent Gaussian fits with measured values for the FWHM of $\Delta E$ =
0.088(5), 0.090(7), and 0.089(6) meV, for Q =
($\frac{1}{2}\frac{1}{2}\frac{3}{2}$), (0.4 0.4 1.3), and (0.31 0.31 1.5),
respectively. The instrumental energy resolution was determined from the FWHM
of the elastic incoherent scattering from plastic to be $\Delta E$ = 0.087(1)
meV and is indicated by the horizontal bar. We conclude that the peaks shown
in Figs. 2(a) and (b) are elastic within our current experimental resolution,
although we can not exclude that the scattering is quasielastic on an energy
scale much smaller than 0.09 meV. We note this possibility because all of the
relevant energy scales in YbBiPt are on the order of the present energy
resolution. However, the systematic absence of scattering at the
($\frac{h}{2}\frac{h}{2}\frac{h}{2}$) points would require that any
quasielastic fluctuations be longitudinal (e.g. in the magnitude of the
moment), and the absence of any change in the magnetic correlation lengths
with temperature would be puzzling.

Evidence for unusual magnetic order in close proximity to a QCP has been found
for other strongly-correlated materials fitting either the conventional SDW or
Kondo-breakdown scenarios. For example, CeCu6-xAux exhibits dynamic short-
range magnetic correlations for $x=x_{\rm{c}}$ = 0.1 (the critical
concentration where non-Fermi-liquid behavior is clearly observed)
Stockert_1998 . For $x$ = 0.2, static short-range AFM order coexists with
long-range AFM order at a different propagation vector Lohneysen_1998 , and
persists well above $T_{\rm{N}}$ derived from specific-heat and AC-
susceptibility measurements Stockert_1997 . This is similar to the temperature
dependence of the broad scattering component in YbBiPt. The presence of both
broad and narrower components of the magnetic scattering may arise from a
number of sources including the competition between magnetic and nonmagnetic
ground states, the possible frustration inherent to the sublattice of side-
sharing tetrahedra of Yb moments, as well as fluctuations associated with the
nearby QCP.

###### Acknowledgements.

We thank R. Flint for useful discussions and gratefully acknowledge the
Missouri University Research Reactor, Helmholtz-Zentrum Berlin für Materialien
und Energie, the National Institute of Standards and Technology, and the U.S.
Dept. of Commerce for the allocated beamtime and support during the
experiments. Work at the Ames Laboratory was supported by the Department of
Energy, Basic Energy Sciences, Division of Materials Sciences & Engineering,
under Contract No. DE-AC02-07CH11358.

## References

  * (1) G. R. Stewart, Rev. Mod. Phys. 56, 755 (1984).
  * (2) G. R. Stewart, Rev. Mod. Phys. 73, 797 (2001).
  * (3) O. Stockert and F. Steglich, Annu. Rev. Condens. Matter Phys. 2, 79 (2011).
  * (4) Q. Si and F. Steglich, Science 329, 1161 (2010).
  * (5) Q. Si, Phys. Status Solidi B 247, 476 (2010).
  * (6) T. Senthil, M. Vojta, and S. Sachdev, Phys. Rev. B 69, 035111 (2004).
  * (7) S. Sachdev, Quantum Phase Transitions (Cambridge University Press, Cambridge, 1999).
  * (8) P. Coleman, Handbook of Magnetism and Advanced Magnetic Materials, edited by H. Kronmüller and S. Parkin (John Wiley and Sons, New York, 2007).
  * (9) J. A. Hertz, Phys. Rev. B 14, 1165 (1976).
  * (10) A. J. Millis, Phys. Rev. B 48, 7183 (1993).
  * (11) O. Stockert, E. Faulhaber, G. Zwicknagl, N. Stüßer, H. S. Jeevan, M. Deppe, R. Borth, R. Küchler, M. Loewenhaupt, C. Geibel, and F. Steglich, Phys. Rev. Lett. 92, 136401 (2004).
  * (12) W. Knafo, S. Raymond, P. Lejay, and J. Flouquet, Nat. Phys. 5, 753 (2009).
  * (13) Q. Si, S. Rabello, K. Ingersent, and J. L. Smith, Nature 413, 804 (2001).
  * (14) S. Friedemann, T. Westerkamp, M. Brando, N. Oeschler, S. Wirth, P. Gegenwart, C. Krellner, C. Geibel, and F. Steglich, Nat. Phys. 5, 465 (2009).
  * (15) S. L. Bud’ko, E. Morosan, and P. C. Canfield, Phys. Rev. B 69, 014415 (2004).
  * (16) P. G. Niklowitz, G. Knebel, J. Flouquet, S. L. Bud’ko, and P. C. Canfield, Phys. Rev. B 73, 125101 (2006).
  * (17) G. M. Schmiedeshoff, E. D. Mun, A. W. Lounsbury, S. J. Tracy, E. C. Palm, S. T. Hannahs, J.-H. Park, T. P. Murphy, S. L. Bud’ko, and P. C. Canfield, Phys. Rev. B 83, 180408 (2011).
  * (18) K. Ishida, D. E. MacLaughlin, B. L. Young, K. Okamoto, Y. Kawasaki, Y. Kitaoka, G. J. Nieuwenhuys, R. H. Heffner, O. O. Bernal, W. Higemoto, A. Koda, R. Kadono, O. Trovarelli, C. Geibel, and F. Steglich, Phys. Rev. B 68, 184401 (2003).
  * (19) C. Stock, C. Broholm, F. Demmel, J. Van Duijn, J. W. Taylor, H. J. Kang, R. Hu, and C. Petrovic, Phys. Rev. Lett. 109, 127201 (2012).
  * (20) P. C. Canfield, J. D. Thompson, W. P. Beyermann, A. Lacerda, M. F. Hundley, E. Peterson, Z. Fisk, and H. R. Ott, J. Appl. Phys. 70, 5800 (1991).
  * (21) Z. Fisk, P. C. Canfield, W. P. Beyermann, J. D. Thompson, M. F. Hundley, H. R. Ott, E. Felder, M. B. Maple, M. A. Lopez de la Torre, P. Visani, and C. L. Seaman, Phys. Rev. Lett. 67, 3310 (1991).
  * (22) R. Movshovich, A. Lacerda, P. C. Canfield, J. D. Thompson, and Z. Fisk, Phys. Rev. Lett. 73, 492 (1994).
  * (23) P. C. Canfield, R. Movshovich, R. A. Robinson, J. D. Thompson, Z. Fisk, W. P. Beyermann, A. Lacerda, M. F. Hundley, R. H. Heffner, D. E. MacLaughlin, F. Trouw, H. R. Ott, Physica B 197, 101 (1994).
  * (24) E. D. Mun, S. L. Bud’ko, C. Martin, H. Kim, M. A. Tanatar, J.-H. Park, T. Murphy, G. M. Schmiedeshoff, N. Dilley, R. Prozorov, and P. C. Canfield, Phys. Rev. B 87, 075120 (2013).
  * (25) R. A. Robinson, A. Purwanto, M. Kohgi, P. C. Canfield, T. Kamiyama, T. Ishigaki, J. W. Lynn, R. Erwin, E. Peterson, and R. Movshovich, Phys. Rev. B 50, 9595 (1994).
  * (26) J. A. Mydosh and P. M. Oppeneer, Rev. Mod. Phys. 83, 1301 (2011).
  * (27) J. Wosnitza, G. Goll, A. D. Bianchi, B. Bergk, N. Kozlova, I. Opahle, S. Elgazzar, M. Richter, O. Stockert, H. v. Löhneysen, T. Yoshino, and T. Takabatake, New J. Phys. 8, 174 (2006).
  * (28) A. Kreyssig, M. G. Kim, J. W. Kim, D. K. Pratt, S. M. Sauerbrei, S. D. March, G. R. Tesdall, S. L. Bud’ko, P. C. Canfield, R. J. McQueeney, and A. I. Goldman, Phys. Rev. B 84, 220408(R) (2011).
  * (29) S. Chadov, X. Qi, J. Kübler, G. H. Fecher, C. Felser, and S.-C. Zhang, Nature Mater. 9, 541 (2010).
  * (30) A. Amato, P. C. Canfield, R. Feyerherm, Z. Fisk, F. N. Gygax, R. H. Heffner, D. E. MacLaughlin, H. R. Ott, A. Schenck, and J. D. Thompson, Phys. Rev. B 46, 3151 (1992).
  * (31) J. W. Lynn, Y. Chen, S. Chang, Y. Zhao, S. Chi, W. Ratcliff, II, B. G. Ueland, and R. W. Erwin, Journal of Research of NIST 117, 61 (2012).
  * (32) LAMP, the Large Array Manipulation Program, http://www.ill.eu/data_treat/lamp/the-lamp-book/
  * (33) R. T. Azuah, L. R. Kneller, Y. Qiu, P. L. W. Tregenna-Piggott, C. M. Brown, J. R. D. Copley, and R. M. Dimeo, J. Res. Natl. Inst. Stan. Technol. 114, 341 (2009).
  * (34) E. D. Mun, Ph.D. Dissertation, Iowa State University, 2013.
  * (35) O. Stockert, H. v. Löhneysen, A. Rosch, N. Pyka, and M. Loewenhaupt, Phys, Rev. Lett. 80, 5627 (1998).
  * (36) H. v. Löhneysen, A. Neubert, T. Pietrus, A. Schröder, O. Stockert, U. Tutsch, M. Loewenhaupt, A. Rosch, and P. Wölfle, Eur. Phys. J. B 5, 447 (1998).
  * (37) O. Stockert, H. v. Löhneysen, A. Schröder, M. Loewenhaupt, N. Pyka, P. L. Gammel and U. Yaron, Physica B 230-232, 247 (1997).