Mark de Berg is supported by the Dutch Research Council (NWO) through
Gravitation-grant NETWORKS-024.002.003. Department for Applied Mathematics,
University of Twente, the<EMAIL_ADDRESS>Department of
Mathematics and Computer Science, TU Eindhoven, the
NetherlandsM.T.d.Berg@tue.nlhttps://orcid.org/0000-0001-5770-3784 Department
of Computer Science, Aalto University, Espoo, Finlandsandor.kisfaludi-
bak@aalto.fihttps://orcid.org/ 0000-0002-6856-2902 Department of Computer
Science, University of Salzburg,
Austriaantonis.skarlatos@plus.ac.athttps://orcid.org/ 0000-0002-7623-9419Part
of the work was done during an internship at the Max Planck Institute for
Informatics in Saarbrücken, Germany. Antonios Antoniadis, Mark de Berg, Sándor
Kisfaludi-Bak, Antonis Skarlatos [100]Theory of computation Design and
analysis of algorithms John Q. Open and Joan R. Access 2 42nd Conference on
Very Important Topics (CVIT 2016) CVIT 2016 CVIT 2016 December 24–27, 2016
Little Whinging, United Kingdom 42 23

# Computing Smallest Convex Intersecting Polygons

Antonios Antoniadis  Mark de Berg  Sándor Kisfaludi-Bak  Antonis Skarlatos

###### Abstract

A polygon $C$ is an _intersecting polygon_ for a set $\mathcal{O}$ of objects
in $\mathbb{R}^{2}$ if $C$ intersects each object in $\mathcal{O}$, where the
polygon includes its interior. We study the problem of computing the minimum-
perimeter intersecting polygon and the minimum-area convex intersecting
polygon for a given set $\mathcal{O}$ of objects. We present an FPTAS for both
problems for the case where $\mathcal{O}$ is a set of possibly intersecting
convex polygons in the plane of total complexity $n$.

Furthermore, we present an exact polynomial-time algorithm for the minimum-
perimeter intersecting polygon for the case where $\mathcal{O}$ is a set of
$n$ possibly intersecting segments in the plane. So far, polynomial-time exact
algorithms were only known for the minimum perimeter intersecting polygon of
lines or of disjoint segments.

###### keywords:

convex hull, imprecise points, computational geometry

##  1 Introduction

Convex hulls are among the most fundamental objects studied in computational
geometry. In fact, the problem of designing efficient algorithms to compute
the convex hull of a planar point set $\mathcal{O}$—the smallest convex set
containing $\mathcal{O}$—is one of the problems that started the field [8,
16]. Since the early days, the problem has been studied extensively, resulting
in practical and provably efficient algorithms, in the plane as well as in
higher dimensions; see the survey by Seidel [18, Chapter 26] for an overview.

A natural generalization is to consider convex hulls for a collection
$\mathcal{O}$ of geometric objects (instead of points) in $\mathbb{R}^{2}$.
Note that the convex hull of a set of polygonal objects is the same as the
convex hull of the vertices of the objects. Hence, such convex hulls can be
computed using algorithms for computing the convex hull of a point set. A
different generalization, which leads to more challenging algorithmic
questions, is to consider the smallest convex set that  _intersects_ all
objects in $\mathcal{O}$. Thus, instead of requiring the convex set to fully
contain each object from $\mathcal{O}$, we only require that it has a non-
empty intersection with each object.

Notice that in case of points, the “smallest” set is well-defined: if convex
sets $C_{1}$ and $C_{2}$ both contain a point set $\mathcal{O}$, then
$C_{1}\cap C_{2}$ also contains $\mathcal{O}$. Hence, the convex hull of a
point set $\mathcal{O}$ can be defined as the intersection of all convex sets
containing $\mathcal{O}$. When $\mathcal{O}$ consists of objects, however,
this is no longer true, and the term “smallest” is ambiguous. In the present
paper we consider two variants: given a set $\mathcal{O}$ of possibly
intersecting convex polygons in $\mathbb{R}^{2}$ of total complexity $n$, find
a convex set of minimum perimeter that intersects all objects in
$\mathcal{O}$, or a convex set of minimum area that intersects all objects in
$\mathcal{O}$.

Observe that a minimum-perimeter connected intersecting set $C$ for
$\mathcal{O}$ must be a convex polygon. To see this, observe that for any
object $o\in\mathcal{O}$ we can select a point $p_{o}\in o\cap C$, and take
the convex hull of these points; the result is a feasible convex polygon whose
perimeter is no longer than that of $C$. Thus the convexity of the solution
could be omitted from the problem statement. This contrasts with the minimum-
area problem, where there is always an intersecting polygon of zero area,
namely, a tree. The convexity requirement is therefore essential in the
problem statement. Note that it is still true that the minimum-area convex
intersecting set is a polygon: given a convex solution, we can again take the
convex hull of the points $p_{o}$ and get a feasible solution whose area is
not greater than the area of the initial convex solution. We also remark that
the two problems typically have different optima. If $\mathcal{O}$ consists of
the three edges of an equilateral triangle, then the minimum-area solution is
a line segment (that is, a degenerate polygon of zero area), whereas the
minimum-perimeter solution is the triangle whose vertices are the midpoints of
the edges.

The problem of computing minimum-area or minimum-perimeter convex intersecting
polygons, as well as several related problems, have already been studied.
Dumitrescu and Jiang [7] considered the minimum-perimeter intersecting polygon
problem. They gave a constant-factor approximation algorithm as well as a PTAS
for the case when the objects in $\mathcal{O}$ are segments or convex
polygons. They achieved a running time of
$n^{O(1)}/\varepsilon+2^{O(1/\varepsilon^{2/3})}n$. They also prove that
computing a minimum-perimeter intersecting polygon for a set $\mathcal{O}$ of
non-convex polygons (or polygonal chains) is NP-hard. For convex input
objects, however, the hardness proof fails. Hence, Dumitrescu and Jiang ask
the following question.

> Question 1. Is the problem of computing a minimum-perimeter intersecting
> polygon of a set of segments NP-hard?

In case of _disjoint_ segments, a minimum-perimeter intersecting polygon can
be found in polynomial time [9, 10], but for intersecting segments the
question is still open.

The problem of computing smallest intersecting polygons for a set
$\mathcal{O}$ of objects has also been studied in works on _imprecise points_.
Now the input is a set of points, but the the exact locations of the points
are unknown. Instead, for each point one is given a region where the point can
lie. One can then ask questions such as: what is the largest possible convex
hull of the imprecise points? And what is the smallest possible convex hull?
If we consider the objects in our input set $\mathcal{O}$ as the regions for
the imprecise points, then the latter question is exactly the same as our
problem of finding smallest intersecting convex sets. In this setup both the
minimum-perimeter and minimum-area problem have been considered, for sets
$\mathcal{O}$ consisting of convex regions of total complexity $n$. There are
exact polynomial-time algorithms for minimum (and maximum) perimeter and area,
for the special case where $\mathcal{O}$ consists of horizontal line segments
or axis-parallel squares [15]. Surprisingly, some of these problems are NP-
hard, such as the _maximum_ -area/perimeter problems for segments. This gave
rise to the study of approximation algorithms and approximation schemes [14].

In some cases, the minimum-perimeter problem can be phrased as a travelling
salesman problem with neighborhoods (TSPN). Here the goal is to find the
shortest closed curve intersecting all objects from the given set
$\mathcal{O}$. In general, an optimal TSPN tour need not be convex, but one
can show that in the case of lines or rays, an optimal tour is always convex:
if a convex polygon intersects a line (or a ray) then its boundary intersects
the line (resp. the ray). Therefore, computing a minimum-perimeter
intersecting polygon of lines (or rays) is the same problem as TSPN with line
neighborhoods (resp. ray neighborhoods). TSPN of lines in $\mathbb{R}^{2}$
admits a polynomial-time algorithm [5]. In higher dimensions, TSPN has a PTAS
for hyperplane neighborhoods [1], but notice that this is not the natural
generalization of the minimum-intersecting polygon problem. Tan [17] proposed
an exact algorithm for TSPN of rays in $\mathbb{R}^{2}$, but there seems to be
an error in the argument; see Appendix A. At the time of writing this article,
we believe that a polynomial-time algorithm for TSPN of rays is not known, but
there is a constant-factor approximation algorithm due to Dumitrescu [6], as
well as a PTAS [7].

##### Our results.

In order to resolve Question 1, we first need to establish a good structural
understanding and a dynamic programming algorithm. It turns out that the
algorithm can also be used for approximation. We give dynamic-programming-
based approximation schemes for the minimum-perimeter and minimum-area convex
intersecting polygon problems. Our first algorithm is a fully polynomial time
approximation scheme (FPTAS) for the minimum-perimeter problem of arbitrary
convex objects of total complexity $n$.

######  Theorem 1.1.

Let $\mathcal{O}$ be a set of convex polygons of total complexity $n$ in
$\mathbb{R}^{2}$ and let opt be the minimum perimeter of an intersecting
convex polygon for $\mathcal{O}$. For any given $\varepsilon>0$, we can
compute an intersecting polygon for $\mathcal{O}$ whose perimeter is at most
$(1+\varepsilon)\cdot\mbox{{\sc opt}}$, in
$O(n^{2.373}/\varepsilon+n/\varepsilon^{8})$ time.

This is a vast improvement over the PTAS given by Dumitrescu and Jiang [7], as
the dependence on $1/\varepsilon$ is only polynomial in our algorithm. Our
approximation algorithms work in a word-RAM model, where input polygons are
defined by the coordinates of their vertices, and where each coordinate is a
word of $O(\log n)$ bits.

We also get a similar approximation scheme for the minimum area problem,
albeit with a slower running time. Here we rely more strongly on the fact that
the objects of $\mathcal{O}$ are convex _polygons_ , and an extension to (for
example) disks is an interesting open question. The minimum-perimeter FPTAS
needs to be adapted to the minimum-area setting.

######  Theorem 1.2.

Let $\mathcal{O}$ be a set of convex polygons of total complexity $n$ in
$\mathbb{R}^{2}$ and let opt be the minimum area of an intersecting convex
polygon for $\mathcal{O}$. For any given $\varepsilon>0$, we can compute a
convex intersecting polygon for $\mathcal{O}$ whose area is at most
$(1+\varepsilon)\cdot\mbox{{\sc opt}}$, in
$O(n^{17}\log(1/\varepsilon)+n^{11}/\varepsilon^{24})$ time.

We remark that both Theorem 1.1 and Theorem 1.2 work if the input has
_polytopes_ instead of polygons, that is, when each object is the intersection
of some half-planes.

While the dynamic programming algorithm developed above is crucial to get an
exact algorithm, we are still several steps from being able to resolve
Question 1. The main challenge here is that the vertices of the optimum
intersecting polygon can be located at arbitrary boundary points in
$\mathcal{O}$, and there is no known way to discretize the problem. We
introduce a subroutine that uses an algorithm of Dror et al. [5] to compute
parts of the minimum-perimeter intersecting polygon that contain no vertices
of input objects. We are able to achieve a polynomial-time algorithm (on a
real-RAM machine) for the minimum perimeter intersecting polygon problem only
when the objects are line segments.

######  Theorem 1.3.

Let $\mathcal{O}$ be a set of $n$ line segments in the plane. Then we can
compute a minimum-perimeter intersecting polygon for $\mathcal{O}$ in
$O(n^{9}\log n)$ time.

If $\texttt{P}\neq\texttt{NP}$, then this gives a direct negative answer to
Question 1. The theorem also extends to the case of rays (this is the scenario
studied by Tan [17]; see Appendix A.

##### Our techniques.

Our approximation algorithms both compute an approximate solution whose
vertices are from some fine grid. To determine a suitable grid resolution, we
need to be able to compute lower bounds on opt, which is non-trivial. It is
also non-trivial to know where to place the grid, such that it is guaranteed
to contain an approximate solution. The problem is that our lower bound gives
us the location of a solution that is a constant-factor approximation, but
this can be far from the location of a $(1+\varepsilon)$-approximation. Hence,
for the minimum-area problem we generate a collection of grids, one of which
is guaranteed to contain a $(1+\varepsilon)$-approximate solution. Finally, we
face some further difficulties since a square grid may be insufficient: the
optimum intersecting polygon may be extremely (exponentially) thin and long,
and of area close to zero. In such cases there is no square grid of polynomial
size that would contain a good solution. These problems are resolved in
Section 2.

Section 3 presents our dynamic programming algorithm for minimum perimeter. In
the dynamic programming the main technical difficulty lies in the fact that it
is not clear what subset of objects should be visited in each subproblem. A
portion of the optimum’s boundary could in principle be tasked with
intersecting an arbitrary subset of $\mathcal{O}$, while some of the objects
in $\mathcal{O}$ need not be intersected by the optimum boundary and will
simply be covered by the interior of the optimum intersecting polygon: a naïve
approach therefore would not yield a polynomial-time algorithm. Our carefully
designed subproblems have a clear corresponding set of objects to “visit”,
using orderings of certain tangents of input objects for this purpose. The
minimum area problem uses a similar dynamic program, see Section 4 for its
details.

Finally, in order to present our exact algorithm in Section 5, we need to
modify our dynamic program to deal with subproblems where the vertices of a
convex chain do not come from a discretized set. In such cases, we have to
find the order in which the objects of $\mathcal{O}$ are visited by the chain.
We are able to prove a specific ordering only in the case when the objects are
line segments. The order then allows us to invoke the algorithm of Dror et al.
[5] in a black-box manner.

##  2 Locating an optimal solution

The algorithms to be presented in subsequent sections need to approximately
know the size and location of a smallest intersecting polygon. We use an
algorithm from [7] to locate the minimum-perimeter intersecting polygon. With
respect to the minimum-area intersecting polygon we prove that either there is
a solution with a constant number of vertices (that can be computed with a
different algorithm), or it is sufficient to consider polygons whose vertices
are from a grid which comes from a polynomial collection of different grids.

##### Locating the minimum-perimeter optimum.

For the minimum-perimeter intersecting polygon of a set $\mathcal{O}$ of
convex objects, Dumitrescu and Jiang [7] present an algorithm $A1$ that, for a
given $\varepsilon_{1}>0$, outputs a rectangle $R$ intersecting all input
objects $\mathcal{O}$ and with perimeter at most
$\frac{4}{\pi}(1+\varepsilon_{1})\mbox{{\sc opt}}$. At a high level, $A1$
guesses an orientation of the rectangle among
$\lceil\frac{\pi}{4\varepsilon_{1}}\rceil$ many discrete orientations and then
uses a linear program to identify the smallest perimeter rectangle of that
orientation that intersects $\mathcal{O}$. In [7] it is described how
Algorithm $A1$ is used to locate an optimal solution if the input objects are
convex polygons. In particular, for any $\varepsilon>0$ running $A1$ with
$\varepsilon_{1}=\frac{\varepsilon}{2+\varepsilon}$ gives a rectangle $R$. Let
$\sigma$ be the square that is concentric and parallel to $R$ and has a side
length of $3\cdot\mathrm{per}(R)$. Then the following holds.

######  Lemma 2.1 (Lemma $3$ in [7]).

Suppose that $\mathrm{per}(R)\geq(1+\varepsilon)\mbox{{\sc opt}}$. Then there
is an optimum polygon $C_{\mathrm{opt}}$ that is covered by $\sigma$.

Algorithm $A1$ needs to solve $O(1/\varepsilon)$ many linear programs with
$O(n)$ variables and $O(n)$ constraints each. Thus $R$ and $\sigma$ can be
found in $O(T_{\mathrm{LP}}(n)/\varepsilon)$ time, where
$O(T_{\mathrm{LP}}(n)$ is the running time of an LP solver with $O(n)$
variables and $O(n)$ constraints. The state-of-the-art LP solver by Jiang et
al. [11] achieves a running time better than $O(n^{2.373})$. Lemma 2.1
directly implies that if
$\mathrm{per}(R)\geq(1+\varepsilon)\mathrm{per}(C_{\mathrm{opt}})$, then

$\displaystyle\mathrm{diam}(C_{\mathrm{opt}})\leq\mathrm{diam}(\sigma)=3\sqrt{2}\mathrm{per}(R)\leq
3\sqrt{2}\frac{4}{\pi}(1+\varepsilon)\mathrm{per}(C_{\mathrm{opt}})=O(\mathrm{diam}(C_{\mathrm{opt}})).$
(1)

##### The shape and location of the minimum-area optimum.

For the rest of this section, let $X$ denote the set of vertices in the planar
arrangement given by $\mathcal{O}$.

######  Lemma 2.2.

Let $C_{\mathrm{opt}}$ be a minimum-area intersecting polygon for the input
$\mathcal{O}$ that has the minimum number of vertices, and among such polygons
has the maximum number of points from $X$ on its boundary. Then for any vertex
$v$ of $C_{\mathrm{opt}}$ that is not in $X$, the relative interior of at
least one side of $C_{\mathrm{opt}}$ adjacent to $v$ contains a point of $X$.

######  Proof 2.3.

Suppose for a contradiction that $v\not\in X$ and that the relative interior
of the sides in $C_{\mathrm{opt}}$ adjacent to $v$ are disjoint from $X$.
Observe that $v$ must be on the boundary of an input object, so it is in the
relative interior of an edge $e$ of an input object, see Fig. 1(i). Then there
exists a vector parallel to $e$ along which we can move $v$ while fixing its
neighboring vertices in $C_{\mathrm{opt}}$, without increasing the area of
$C_{\mathrm{opt}}$. This movement can be continued until we hit a point in
$X$, or the angle of the polygon becomes $\pi$ at $v_{1}$ or $v_{2}$. As a
result, we end up with a feasible polygon $S$ whose area is no greater than
that of $C_{\mathrm{opt}}$, and it has one less vertex or at least one more
point of $X$ on its boundary. This contradicts the properties of
$C_{\mathrm{opt}}$.

Figure 1: (i) If $v$ and adjacent sides of $C_{\mathrm{opt}}$ are disjoint
from $X$, then we can slide $v$ without increasing the area of
$C_{\mathrm{opt}}$. (ii) The points of $Q$ (green) and their circumscribed
ellipse $E$.

The following lemma is the key to the success of the algorithm.

######  Lemma 2.4.

For any given set of input polygons $\mathcal{O}$ and $0<\varepsilon<1$ there
is an intersecting polygon $C$ of area $(1+\varepsilon)\mbox{{\sc opt}}$ which
either has at most $8$ vertices, or its vertices are in a rectangular grid $G$
of size $O(1/\varepsilon^{3})\times O(1/\varepsilon^{3})$ where $G$ belongs to
a collection $\mathcal{G}$ of grids that can be generated in polynomial time.

######  Proof 2.5.

Let $C_{\mathrm{opt}}$ be a minimum-area convex intersecting polygon for the
input $\mathcal{O}$ that has the minimum number of vertices, and among such
polygons has the maximum number of points from $X$ on its boundary. Notice
that if $C_{\mathrm{opt}}$ has $0$ area, then it is a doubled segment, and
thus has only $2$ vertices.

Suppose now that $C_{\mathrm{opt}}$ has at least $9$ vertices, and it has
positive area. By Lemma 2.2, $\partial C_{\mathrm{opt}}$ has at least four
points from $X$ that are on four distinct edges of $C_{\mathrm{opt}}$. Let
$Q=C_{\mathrm{opt}}\cap X$. Since the area of $C_{\mathrm{opt}}$ is not $0$
and $Q$ contains points on four distinct edges, we have that $Q$ forms a
convex polygon of positive area.

Let $E$ be the minimum-area ellipse (of any orientation) covering $Q$. Such an
ellipse must contain at most $5$ points from $Q$. Therefore $E$ is uniquely
defined by at most $5$ vertices from $Q$, see Fig. 1(ii). Consequently, we can
generate a set $\mathcal{B}$ of candidate ellipses in time $O(|X|^{5})$ time
that is guaranteed to contain $E$. As a consequence of John’s theorem [12, 2]
we can scale $E$ by a factor $1/2$ from the center of $E$ to get an ellipse
$E^{\prime}$ that is contained in $E$.

Next, we apply an affinity that makes $E$ into a circle. Note that the
transformation changes the area of all polygons by the same multiplicative
constant, therefore the transformation preserves optima and multiplicative
approximations of area. We will keep using our previous notations on this
transformed instance for the rest of this proof. Without loss of generality
assume that $E$ is the unit radius circle centered at the origin.
Consequently, $E^{\prime}$ is the unit diameter circle centered at the origin.

The points of $Q$ subdivide $\partial C_{\mathrm{opt}}$ into $|Q|$ distinct
sections. A section is called a _spike_ if it contains some vertex of
$C_{\mathrm{opt}}$ outside the disk of radius $32/\varepsilon$. If $v$ is a
vertex, then let $S(v)$ denote the convex hull of the section of $v$.

Suppose that $C_{\mathrm{opt}}$ has a vertex $v$ that is outside the disk of
radius $32/\varepsilon$. We will show that in this case there is a
$(1+\varepsilon)$-approximate solution that has at most $8$ vertices. Let
$q_{v},q^{\prime}_{v}\in Q$ be the endpoints of the section of $v$. Notice
that $C_{\mathrm{opt}}$ covers the triangle $vq_{v}q^{\prime}_{v}$. Since
$E^{\prime}$ is contained in $C_{\mathrm{opt}}$, we know that the half-cone
given by the rays $vq_{v}$ and $vq^{\prime}_{v}$ contains $E^{\prime}$. Thus
the shape given by the touching segments from $v$ to $E^{\prime}$ and the disk
of $E^{\prime}$ is covered by $C_{\mathrm{opt}}$, see Fig. 2(i). This shape
has area area at least $16/\varepsilon$. Consequently, if $C_{\mathrm{opt}}$
has a spike, then

$\mathrm{area}(C_{\mathrm{opt}})\geqslant 16/\varepsilon.$ (2)

We now claim that $C_{\mathrm{opt}}$ has at most two sections which have a
vertex at distance strictly greater than $2$ from the origin. To prove the
claim, suppose the contrary, that $v,w,x$ are vertices in disjoint sections,
and each of $v,w,x$ are at distance strictly greater than $2$ from the origin.
It follows that each of the three portions of $\partial C_{\mathrm{opt}}$
defined by $v,w,x$ must contain some point of $Q$, and in particular, some
point that falls in the unit disk. Since the triangle $T$ given by $v,w,x$ is
covered by $C_{\mathrm{opt}}$, we have that each side of $T$ must intersect
the unit disk (as otherwise at least one of the three boundary portions would
be disjoint from the unit disk). Assume without loss of generality that $T$
has its largest angle at $v$, i.e., it has angle at least $\pi/3$ at $v$. Then
it follows that $v$ is at distance at most $2$ from the origin, which is a
contradiction. This concludes the proof of our claim.

Figure 2: (i) A spike at vertex $v$. The section convex hull $S(v)$ is shaded
with red. (ii) Building blocks of a constant-size feasible polygon with at
most two spikes and the radius $2$ square. The polygon $C_{0}$ is shaded blue,
and the red falling pattern indicates the cone $C_{w}$.

Our claim implies that there are vertices $v,w\in C_{\mathrm{opt}}$ such that
$C_{\mathrm{opt}}$ can be covered by the union of the sections $S(v)$, $S(w)$,
and the square $[-2,2]\times[-2,2]$. Let $C_{0}=S(v)\cup
S(w)\cup[-2,2]\times[-2,2]$. Note that $C_{0}$ is a polygon covering
$C_{\mathrm{opt}}$. Consider the (potentially unbounded polygon) $C_{v}$ whose
sides are the sides of the spike, where we extend the sides adjacent to
$q_{v}$ and $q^{\prime}_{v}$ until they meet (or into rays), see Fig. 2(ii)
for an illustration. Notice that $C_{v}$ covers $C_{\mathrm{opt}}$. The
polygon $C=C_{0}\cap C_{v}\cap C_{w}$ is convex and covers $C_{\mathrm{opt}}$,
and
$\mathrm{area}(C)-\mathrm{area}(C_{\mathrm{opt}})\leqslant\mathrm{area}([-2,2]\times[-2,2])=16$.
Thus if $C_{\mathrm{opt}}$ has a spike, then by the bound (2) the polygon $C$
has area at most
$\mathrm{area}(C_{\mathrm{opt}})+16\leqslant(1+\varepsilon)\mathrm{area}(C_{\mathrm{opt}})$.
Observe that $C$ has at most $8$ vertices: it has at most $2+2$ vertices on
the spikes. Every further vertex is either an original vertex of the square,
or it arises after some side of $C_{v}$ or $C_{w}$ incident to $Q$ cuts off at
least one vertex, keeping the number of vertices unchanged.

It remains to show that if $|V(C_{\mathrm{opt}})|\geqslant 9$ and all vertices
of $C_{\mathrm{opt}}$ are within distance $32/\varepsilon$ from the origin,
then we can generate a polynomial-size grid set $\mathcal{G}$ with the desired
properties. Recall that we can generate a set $\mathcal{B}$ of candidate
circumscribed ellipses of $Q$ in time $O(|X|^{5})=O(n^{10})$ time, that is,
for all at most 5-tuples of $X$ we compute the corresponding circumscribed
ellipse and the affine transform to make the ellipse into a circle. For each
ellipse the computations and the transformation takes $O(1)$ time. We set the
circle’s radius as unit and fix a coordinate system centered at the circle
center. Let $G$ be the square grid that subdivides each side of the square
$\sigma=[-32/\varepsilon,32/\varepsilon]\times[-32/\varepsilon,32/\varepsilon]$
into $k=\lfloor 2^{16}/\varepsilon^{3}\rfloor$ equal segments. The resulting
grid $G$ has size $k\times k=O(1/\varepsilon^{3})\times O(1/\varepsilon^{3})$.
Let $\mathcal{G}$ be the set of $O(n^{10})$ grids generated this way. For the
sake of simplifying the proof and the illustrations, we apply the affine
transform to the entire instance, but we need not do that transformation to
generate $G$: each ellipse defines a rectangular grid $G$ on the original
plane whose points we can access in constant time.

It remains to show that there is a polygon $C$ with area at most
$(1+\varepsilon)\mbox{{\sc opt}}$ such that $V(C)\subset G$ for some
$G\in\mathcal{G}$. Let $G$ be the square grid corresponding to the true
circumscribed ellipse of $Q$. Consider the grid cells containing
$V(C_{\mathrm{opt}})$; let $C$ be the convex hull of these cells. Notice that
$|V(C)|\leqslant 4|V(C_{\mathrm{opt}})|$. Moreover, if $\delta$ is the cell
diameter of $G$, then $C$ is covered by the Minkowski sum
$C_{\mathrm{opt}}\oplus B_{\delta}$, where $B_{\delta}$ is the disk of radius
$\delta$. Thus we have that

$\displaystyle\mathrm{area}(C)$
$\displaystyle\leqslant\mathrm{area}(C_{\mathrm{opt}}\oplus B_{\delta})$
$\displaystyle=\mathrm{area}(C_{\mathrm{opt}})+\mathrm{per}(C_{\mathrm{opt}})\cdot\delta+\mathrm{area}(B_{\delta})$
$\displaystyle\leqslant\mathrm{area}(C_{\mathrm{opt}})+\delta\cdot 4\cdot
64/\varepsilon+\delta^{2}\pi,$

where the last inequality uses that the perimeter of a convex polygon is less
than the perimeter of any covering simple polygon: in this case the square
$\sigma$ covers $C$. Since
$\mathrm{area}(C_{\mathrm{opt}})\geqslant\mathrm{area}(E^{\prime})=\pi/4$ and
$\delta=\sqrt{2}\cdot\frac{64/\varepsilon}{\lfloor
2^{16}/\varepsilon^{3}\rfloor}<\varepsilon^{2}/2^{9}$, we can continue the
inequality chain as follows:

$\mathrm{area}(C)\leqslant\mathrm{area}(C_{\mathrm{opt}})+2^{8}\delta/\varepsilon+\delta^{2}\pi<\mathrm{area}(C_{\mathrm{opt}})+\varepsilon/2+\varepsilon/2^{16}<(1+\varepsilon)\mathrm{area}(C_{\mathrm{opt}}),$

concluding the proof.

##  3 An FPTAS for the minimum-perimeter problem of convex objects in the
plane

Let $\mathcal{O}$ be a set of $n$ convex objects in the plane for which we
want to compute a minimum-perimeter convex intersecting polygon. We assume
that $\mathcal{O}$ cannot be be stabbed by a single point—this is easy to test
without increasing the total running time. Since a minimum-perimeter
intersecting polygon is necessarily convex, we will from now on drop the
adjective “convex” from our terminology. We do this even when referring to
convex intersecting polygons that are not necessarily of minimum perimeter.

In the previous section we have seen that for any $\varepsilon>0$, we can find
a feasible rectangle $R$ and a square $\sigma$ with the following property:
Either $\mathrm{per}(R)\leq(1+\varepsilon)\mbox{{\sc opt}}$, or
$C_{\mathrm{opt}}\subseteq\sigma$ with
$\mathrm{diam}(C_{\mathrm{opt}})=\Omega(1)\mathrm{diam}(\sigma)$. Next we
describe an algorithm that, given a parameter $\varepsilon>0$ and a
corresponding square $\sigma$, outputs an intersecting polygon
$C^{*}\subseteq\sigma$ for $\mathcal{O}$ such that if
$\mathrm{per}(R)\geq(1+\varepsilon)\mathrm{per}(C_{\mathrm{opt}})$ then
$\mathrm{per}(C^{*})\leqslant(1+\varepsilon)\mbox{{\sc opt}}$, where
$\mbox{{\sc opt}}=\mathrm{per}(C_{\mathrm{opt}})$ (cf. Lemma 2.1 and Equation
1). Finally, we output either $R$ or $C^{*}$, whichever has smaller perimeter.

Our algorithm starts by partitioning $\sigma$ into a regular grid $G(\sigma)$
of $O(1/\varepsilon^{2})$ cells of edge length at most
$(\varepsilon/8)\cdot\mbox{{\sc opt}}$. We say that a convex polygon is a
_grid polygon_ if its vertices are grid points from $G(\sigma)$. The following
observation is standard, but for completeness we include a proof. Suppose
$\sigma$contains an optimal solution $C_{\mathrm{opt}}$. Let $C(\sigma)$ be a
minimum-perimeter grid polygon that is an intersecting polygon for
$\mathcal{O}$. Then
$\mathrm{per}(C(\sigma))\leqslant(1+\varepsilon)\cdot\mbox{{\sc opt}}$.

######  Proof 3.1.

Let $U$ be the union of all grid cells that intersect $C_{\mathrm{opt}}$, and
let $Z$ be a square of edge length $(\varepsilon/4)\cdot\mbox{{\sc opt}}$,
centered at the origin. Then $U$ is contained in the Minkowski sum
$C_{\mathrm{opt}}\oplus Z$. Since $C_{\mathrm{opt}}\oplus Z$ is convex, this
implies that the convex hull $\mbox{\sc ch}(U)$ of $U$, which is a grid
polygon that is an intersecting polygon for $\mathcal{O}$, is contained in
$C_{\mathrm{opt}}\oplus Z$. Because the perimeter of a Minkowski sum of two
convex objects equals the sum of the perimeters of the objects, we have

$\mathrm{per}(C(\sigma))\leqslant\mathrm{per}(\mbox{\sc
ch}(U))\leqslant\mathrm{per}(C_{\mathrm{opt}})+\mathrm{per}(Z)=(1+\varepsilon)\cdot\mbox{{\sc
opt}}.$

Next we describe an algorithm to compute a minimum-perimeter grid polygon
$C(\sigma)$ that is an intersecting polygon for $\mathcal{O}$.

First, we “guess” the lexicographically smallest vertex $v_{\mathrm{bot}}$ of
$C(\sigma)$, see Figure 3(i). We can guess $v_{\mathrm{bot}}$ in
$O(1/\varepsilon^{2})$ different ways. For each possible guess we will find
the best solution (if it exists), and then we report the best solution found
over all guesses.

Now consider a fixed guess for the lexicographically smallest vertex
$v_{\mathrm{bot}}$ of $C(\sigma)$. With a slight abuse of notation we will use
$C(\sigma)$ to denote a minimum-perimeter grid polygon that is an intersecting
polygon of $\mathcal{O}$ and that has $v_{\mathrm{bot}}$ as lexicographically
smallest vertex. (If the polygon $C(\sigma)$ does not exist, the algorithm
described below will detect this.) We will compute $C(\sigma)$ by dynamic
programming.

The vertices of $C(\sigma)$ are grid points in the region
$h^{+}\setminus\rho_{0}$, where $h^{+}$ is the closed half-plane above the
horizontal line through $v_{\mathrm{bot}}$ and $\rho_{0}$ is the horizontal
ray emanating from $v_{\mathrm{bot}}$ and pointing to the left. Let $V$ be the
set of such grid points, excluding $v_{\mathrm{bot}}$. We first order the
points from $V$ in angular order around $v_{\mathrm{bot}}$. More precisely,
for a point $v\in V$, let $\phi(v)$ denote the angle over which we have to
rotate $\rho_{0}$ in clockwise direction until we hit $v$. For two points
$v,w\in V$, we write $v\prec w$ if $\phi(v)<\phi(w)$. Let
$V^{+}:=V\cup\\{v_{\mathrm{bot}},\overline{v}_{\mathrm{bot}}\\}$, where
$\overline{v}_{\mathrm{bot}}$ is a copy of $v_{\mathrm{bot}}$, and define
$v_{\mathrm{bot}}\prec v$ and $v\prec\overline{v}_{\mathrm{bot}}$ for all
$v\in V$. The copy $\overline{v}_{\mathrm{bot}}$ serves to distinguish the
start and the end vertex of the clockwise circular sequence of vertices of
$C(\sigma)$. Note that if
$v_{\mathrm{bot}},v_{1},\ldots,v_{k},\overline{v}_{\mathrm{bot}}$ denotes this
circular sequence then $v_{\mathrm{bot}}\prec v_{1}\prec\cdots\prec
v_{k}\prec\overline{v}_{\mathrm{bot}}$ (since $C(\sigma)$ will never have two
vertices that make the same angle with $v_{\mathrm{bot}}$).

We now describe our dynamic-programming algorithm. Consider a polyline from
$v_{\mathrm{bot}}$ to some point $v\in V$. We say that this polyline is a
_convex chain_ if, together with the line segment $vv_{\mathrm{bot}}$, it
forms a convex polygon. We denote the convex polygon induced by such a chain
$\Gamma$ by $C(\Gamma)$. The problem we now wish to solve is as follows:

> Compute a minimum-length convex chain $\Gamma^{*}$ from $v_{\mathrm{bot}}$
> to $\overline{v}_{\mathrm{bot}}$ such that $C(\Gamma^{*})$ is an
> intersecting polygon for $\mathcal{O}$.

Our dynamic-programming algorithm uses the partial order $\prec$ defined
above. We now want to define a subproblem for each point $v\in V^{+}$, which
is to find the “best” chain $\Gamma_{v}$ ending at $v$. For this to work, we
need to know which objects from $\mathcal{O}$ should be covered by the partial
solution $C(\Gamma_{v})$. This is difficult, however, because objects that
intersect the ray from $v_{\mathrm{bot}}$ and going through $v$ could either
be intersected by $C(\Gamma_{v})$ or by the part of the solution that comes
after $v$. To overcome this problem we let the subproblems be defined by the
last edge on the chain, instead of by the last vertex. This way we can decide
which objects should be covered by a partial solution, as explained next.

Figure 3: (i) The wedge defined by $\rho_{0}$ and $\rho(w)$ is shown in light
grey. Objects in $\mathcal{O}(v,w)$ are red, objects in
$\mathcal{O}\setminus\mathcal{O}(v,w)$ are blue. (ii) The partial solution
$C(\Gamma)$ must be contained in the red region, while $C\setminus C(\Gamma)$
must lie in the blue region. There are four situations, depending on whether
the angle between $\rho_{0}$ and $\rho(w)$ is acute or not, and whether the
line containing $vw$ intersects $\rho_{0}$ or not.

Consider a convex chain from $v_{\mathrm{bot}}$ to a point $w\in V^{+}$ whose
last edge is $vw$. Let $\rho(w)$ be the ray emanating from $v_{\mathrm{bot}}$
in the direction of $w$, and let $\rho^{*}(w)$ be the part of the ray starting
at $w$. For $w=\overline{v}_{\mathrm{bot}}$ we define $\rho(w)$ to be the
horizontal ray emanating from $v_{\mathrm{bot}}$ and going to the right, and
we define $\rho^{*}(w)=\rho(w)$. For an object $o_{i}\in\mathcal{O}$ that
intersects $\rho^{*}(w)$, let $\ell_{w}(o_{i})$ be a line that is tangent to
$o_{i}$ at the first intersection point of $\rho^{*}(w)$ with $o_{i}$. We now
define the set $\mathcal{O}(v,w)$ to be the subset of objects
$o_{i}\in\mathcal{O}$ such that one of the following conditions is satisfied;
see also Figure 3(i).

  1. (i)

$o_{i}$ intersects the wedge defined by $\rho_{0}$ and $\rho(w)$, but not
$\rho(w)$ itself; or

  2. (ii)

$o_{i}$ intersects $v_{\mathrm{bot}}w$; or

  3. (iii)

$o_{i}$ intersects $\rho^{*}(w)$ but not $v_{\mathrm{bot}}w$, and the tangent
line $\ell_{w}(o_{i})$ intersects the half-line containing $vw$ and ending at
$w$.

The next lemma shows that we can use the sets $\mathcal{O}(v,w)$ to define our
subproblems.

######  Lemma 3.2.

Let $C$ be any convex polygon that is an intersecting polygon for
$\mathcal{O}$ and that has $v_{\mathrm{bot}}$ as lexicographically smallest
vertex and $vw$ as one of its edges. Let $\Gamma_{w}$ be the part of $\partial
C$ from $v_{\mathrm{bot}}$ to $w$ in clockwise direction. Then all objects in
$\mathcal{O}(v,w)$ intersect $C(\Gamma_{w})$ and all objects in
$\mathcal{O}\setminus\mathcal{O}(v,w)$ intersect $C\setminus C(\Gamma_{w})$.

######  Proof 3.3.

Because $C$ is convex, it must lie in $h^{+}$ (the closed half-plane above the
horizontal line though $v_{\mathrm{bot}}$) and in the region to the right of
the line $\ell(v,w)$ through $v$ and $w$ and directed from $v$ to $w$. This
region is split into two regions by $\rho(w)$; the region to the left of
$\rho(w)$ contains $C(\Gamma_{w})$ and the region to the right of $\rho(w)$
contains $C\setminus C(\Gamma_{w})$. See Figure 3(ii) for various possible
configurations.

Consider an object $o_{i}\in\mathcal{O}(v,w)$. If $o_{i}$ is in
$\mathcal{O}(v,w)$ because of condition (i), then it cannot intersect
$C\setminus C(\Gamma_{w})$ and, hence, it must intersect $C(\Gamma_{w})$. If
$o_{i}$ is in $\mathcal{O}(v,w)$ because of condition (ii), then trivially
$o_{i}$ intersects $C(\Gamma_{w})$. Finally, if $o_{i}$ is in
$\mathcal{O}(v,w)$ because of condition (iii) then again it cannot intersect
$C\setminus C(\Gamma_{w})$, and so it must intersect $C(\Gamma_{w})$.

On the other hand, suppose that $o_{i}\not\in\mathcal{O}(v,w)$. If $o_{i}$
does not intersect $\rho(w)$ then this means that $o_{i}$ does not intersect
the wedge defined by $\rho_{0}$ and $\rho(w)$. Hence, it cannot intersect
$C(\Gamma_{w})$ and so it must intersect $C\setminus C(\Gamma_{w})$. If
$o_{i}$ intersects $\rho(w)$ then the reason it is not in $\mathcal{O}(v,w)$
is that the tangent line $\ell_{w}(o_{i})$ does not intersect the half-line
containing $vw$ and ending at $w$, which means the tangent separates $o_{i}$
from $C(\Gamma_{w})$. Hence, $o_{i}$ must intersect $C\setminus
C(\Gamma_{w})$.

We can now state our dynamic program. To this end we define, for two points
$v,w\in V^{+}$ with $v\prec w$, a table entry $A[v,w]$ as follows.
$A[v,w]$ := the minimum length of a convex chain $\Gamma$ from
$v_{\mathrm{bot}}$ to $w$ whose last edge is $vw$ and such that all objects in
$\mathcal{O}(v,w)$ intersect $C(\Gamma)$,
where the minimum is $\infty$ if no such chain exists. Lemma 3.2 implies the
following. Let $\Gamma^{*}$ be a shortest convex chain from $v_{\mathrm{bot}}$
to $\overline{v}_{\mathrm{bot}}$ such that $C(\Gamma^{*})$ is an intersecting
polygon for $\mathcal{O}$. Then
$\mathrm{length}(\Gamma^{*})=\min\\{A[v,\overline{v}_{\mathrm{bot}}]:v\in
V\mbox{ and }\mathcal{O}(v,\overline{v}_{\mathrm{bot}})=\mathcal{O}\\}$.

######  Proof 3.4.

Consider any $v\in V$ such that
$\mathcal{O}(v,\overline{v}_{\mathrm{bot}})=\mathcal{O}$. By definition of
$A[v,\overline{v}_{\mathrm{bot}}]$, there is a convex chain $\Gamma$ from
$v_{\mathrm{bot}}$ to $\overline{v}_{\mathrm{bot}}$ such that $C(\Gamma)$ is
an intersecting polygon for $\mathcal{O}$. Hence,
$\mathrm{length}(\Gamma^{*})\leqslant\min\\{A[v,\overline{v}_{\mathrm{bot}}]:v\in
V\mbox{ and }\mathcal{O}(v,\overline{v}_{\mathrm{bot}})=\mathcal{O}\\}$.

Conversely, let $\Gamma^{*}$ be a minimum-length convex chain from
$v_{\mathrm{bot}}$ to $\overline{v}_{\mathrm{bot}}$ such that $C(\Gamma^{*})$
is an intersecting polygon for $\mathcal{O}$. Let $v$ be the vertex preceding
$\overline{v}_{\mathrm{bot}}$ on $\Gamma^{*}$. By Lemma 3.2 all objects in
$\mathcal{O}\setminus\mathcal{O}(v,\overline{v}_{\mathrm{bot}})$ intersect
$C(\Gamma^{*})\setminus C(\Gamma^{*}_{\overline{v}_{\mathrm{bot}}})$, where
$\Gamma^{*}_{\overline{v}_{\mathrm{bot}}}$ is the part of $\Gamma^{*}$ from
$v_{\mathrm{bot}}$ to $\overline{v}_{\mathrm{bot}}$. But trivially
$\Gamma^{*}=\Gamma^{*}_{\overline{v}_{\mathrm{bot}}}$ and so
$C(\Gamma^{*})\setminus
C(\Gamma^{*}_{\overline{v}_{\mathrm{bot}}})=\emptyset$. Since $C(\Gamma^{*})$
is an intersecting polygon for $\mathcal{O}$, this implies that
$\mathcal{O}\setminus\mathcal{O}(v,\overline{v}_{\mathrm{bot}})=\emptyset$.
Hence, $\mathcal{O}=\mathcal{O}(v,\overline{v}_{\mathrm{bot}})$, and so
$\mathrm{length}(\Gamma^{*})\geqslant\min\\{A[v,\overline{v}_{\mathrm{bot}}]:v\in
V\mbox{ and }\mathcal{O}(v,\overline{v}_{\mathrm{bot}})=\mathcal{O}\\}$.

Hence, if we can compute all table entries $A[v,w]$ then we have indeed solved
our problem. (The lemma only tells us something about the value of an optimal
solution, but given the table entries $A[v,w]$ we can compute the solution
itself in a standard way.)

The entries $A[v,w]$ can be computed using the following lemma. Define
$\Delta(v_{\mathrm{bot}},v,w)$ to be the triangle with vertices
$v_{\mathrm{bot}},v,w$.

######  Lemma 3.5.

Let $v,w\in V^{+}$ with $v\prec w$. Let $V(v,w)$ be the set of all points
$u\in V\cup\\{v_{\mathrm{bot}}\\}$ with $u\prec v$ such that $u$ lies below
the line $\ell(v,w)$ through $v$ and $w$ and such that all objects in
$\mathcal{O}(v,w)\setminus\mathcal{O}(u,v)$ intersect
$\Delta(v_{\mathrm{bot}},v,w)$. Then

$A[v,w]=\\!\left\\{\begin{array}[]{ll}|v_{\mathrm{bot}}w|&\mbox{if
$v\\!=\\!v_{\mathrm{bot}}$ and all objects in $\mathcal{O}(v,w)$ intersect
$v_{\mathrm{bot}}w$}\\\ \infty&\mbox{if $v\\!=\\!v_{\mathrm{bot}}$ and not all
objects in $\mathcal{O}(v,w)$ intersect $v_{\mathrm{bot}}w$}\\\
|vw|\\!+\\!\\!\min\limits_{u\in
V(v,w)}\\!\\!A[u,v]&\mbox{otherwise}\end{array}\right.$

######  Proof 3.6.

The first two cases immediately follow from the definition of $A[v,w]$, since
for $v=v_{\mathrm{bot}}$ we have $\Gamma=v_{\mathrm{bot}}w$ and so
$C(\Gamma)=v_{\mathrm{bot}}w$.

To prove the third case, let $\Gamma^{*}$ be a minimum-length convex chain
from $v_{\mathrm{bot}}$ to $w$ whose last edge is $vw$ and such that all
objects in $\mathcal{O}(v,w)$ intersect $C(\Gamma^{*})$. Let $A[v,w]$ be the
value computed by the recursive formula given in the lemma. We must prove that
$A[v,w]=\mathrm{length}(\Gamma^{*})$.

Let $u^{*}$ be the vertex preceding $v$ on $\Gamma^{*}$. Then $u^{*}\prec v$
and (because of convexity) $u^{*}$ must lie below $\ell(v,w)$. Now consider an
object $o_{i}\in\mathcal{O}(v,w)\setminus\mathcal{O}(u^{*},v)$. By Lemma 3.2
it must be intersected by $\Delta(v_{\mathrm{bot}},v,w)$, since
$\Delta(v_{\mathrm{bot}},v,w)=C(\Gamma^{*})\setminus C(\Gamma^{*}\setminus
vw)$. Hence, $u^{*}\in V(v,w)$. Moreover,
$A[u^{*},v]=\mathrm{length}(\Gamma^{*}\setminus vw)$ by induction. Hence,

$A[v,w]:=|vw|+\min\limits_{u\in
V(v,w)}A[u,v]\leqslant|vw|+A[u^{*},v]=\mathrm{length}(\Gamma^{*}).$

On the other hand, for any $u\prec v$ with $A[u,v]\neq\infty$ there is, by
induction, a convex chain of length $A[u,v]$ starting at $v_{\mathrm{bot}}$
whose last edge is $uv$ that intersects all objects in $\mathcal{O}(u,v)$. If
$u\in V(v,w)$ then we can extend this chain to a convex chain $\Gamma$
starting at $v_{\mathrm{bot}}$ whose last edge is $vw$ and such that all
objects in $\mathcal{O}(v,w)$ intersect $C(\Gamma)$. Hence, for any $u\in
V(v,w)$ there is a convex chain $\Gamma$ from $v_{\mathrm{bot}}$ to $w$ whose
least edge is $vw$ and such that $C(\Gamma)$ intersects all objects in
$\mathcal{O}(v,w)$. Thus $A[v,w]:=|vw|+\min\limits_{u\in V(v,w)}A[u,v]$ is at
least the minimum length of such a chain.

This finishes the correctness proof of the third case.

Putting everything together, we can finish the proof of Theorem 1.1.

######  Proof 3.7 (Proof of Theorem 1.1).

We first use algorithm $A1$ from [7] to compute the rectangle $R$ and the
square $\sigma$, which as discussed can be done in $O(n^{2.373}/\varepsilon)$
time. For a square $\sigma$ we guess the vertex $v_{\mathrm{bot}}$ in
$O(1/\varepsilon^{2})$ different ways.

For each guess we run the dynamic-programming algorithm described above. There
are $O(1/\varepsilon^{4})$ entries $A[u,v]$ in the dynamic-programming table.
The most time-consuming computation of a table entry is in the third case of
Lemma 3.5. Here we need to compute the set $\mathcal{O}(v,w)$, which can be
done in $O(n)$ time by checking every $o_{i}\in\mathcal{O}$. For each of the
$O(1/\varepsilon^{2})$ points with $u\prec v$ such that $u$ lies below the
line $\ell(v,w)$ we then check in $O(n)$ time if all objects in
$\mathcal{O}(v,w)\setminus\mathcal{O}(u,v)$ intersect
$\Delta(v_{\mathrm{bot}},v,w)$, so that we can compute $A[v,w]$. Hence,
computing $A[v,w]$ takes $O(n/\varepsilon^{2})$ time, which implies that the
whole dynamic program needs $O(n/\varepsilon^{6})$ time.

Thus the algorithm takes $O(n^{2.373}/\varepsilon)+O(1/\varepsilon^{2})\cdot
O(n/\varepsilon^{6})=O(n^{2.373}/\varepsilon+n/\varepsilon^{8})$ time.

######  Remark 3.8.

Although Theorem 1.1 is stated only for the case where $\mathcal{O}$ is a set
of convex polygons, it is not too hard to extend it to other convex objects,
for example disks: one just needs to replace the approximate rectangle-finding
linear program of Dumitrescu and Jiang [7] with some other polynomial-time
algorithm to find an (approximate) minimum perimeter intersecting rectangle in
each of the $O(1/\varepsilon)$ orientations.

##  4 An FPTAS for the minimum-area convex intersecting polygon

Due to Lemma 2.4, either there exists an approximate solution with at most $8$
vertices, or it is sufficient to compute the minimum-area convex intersecting
polygon whose vertices are in a grid $G\in\mathcal{G}$. Since we have no way
to distinguish between these outcomes, we will compute a minimum feasible
solution of at most $8$ vertices, as well as a minimum feasible polygon (if it
exists) in each grid $G\in\mathcal{G}$, and simply return the smallest area
polygon that we have found.

In Section 4.1 we show how to compute an (approximate) minimum area polygon
with at most $8$ vertices with known algebraic methods in
$O(n^{17}\log(1/\varepsilon))$ time; here we concentrate on adapting our
dynamic programming for the minimum-perimeter problem. Let us fix a grid
$G\in\mathcal{G}$. Keeping the notations as before, we see that everything up
to (and including) Lemma 3.2 still holds. We define the subproblems as
follows.
$A[v,w]$ := the minimum area in the convex hull $C(\Gamma)$ of a convex chain
$\Gamma$ from $v_{\mathrm{bot}}$ to $w$ whose last edge is $vw$ and such that
all objects in $\mathcal{O}(v,w)$ intersect $C(\Gamma)$,
where the minimum is $\infty$ if no such chain exists. The proof of the
following observation is the same as the proof of Observation 3, one only
needs to change all mentions of length or perimeter of a convex chain to the
area of the convex hull of the chain.

Let $\Gamma^{*}$ be a convex chain from $v_{\mathrm{bot}}$ to
$\overline{v}_{\mathrm{bot}}$ where $C(\Gamma^{*})$ has minimum area and it is
an intersecting polygon for $\mathcal{O}$. Then
$\mathrm{area}(C(\Gamma^{*}))=\min\\{A[v,\overline{v}_{\mathrm{bot}}]:v\in
V\text{ and }\mathcal{O}(v,\overline{v}_{\mathrm{bot}})=\mathcal{O}\\}$.

The recursion also works analogously: we only need to change the starting
value, and in the recursive step we add the area of the triangle corresponding
to the new segment instead of its length. The proof is again analogous to the
minimum-area variant (to Lemma 3.5).

######  Lemma 4.1.

Let $v,w\in V^{+}$ with $v\prec w$. Let $V(v,w)$ be the set of all points
$u\in V\cup\\{v_{\mathrm{bot}}\\}$ with $u\prec v$ such that $u$ lies below
the line $\ell(v,w)$ through $v$ and $w$ and such that all objects in
$\mathcal{O}(v,w)\setminus\mathcal{O}(u,v)$ intersect
$\Delta(v_{\mathrm{bot}},v,w)$. Then

$A[v,w]=\begin{cases}0&\parbox{170.71652pt}{if $v=v_{\mathrm{bot}}$ and all
objects\\\ in $\mathcal{O}(v,w)$ intersect
$v_{\mathrm{bot}}w$}\\\\[11.38109pt] \infty&\parbox{170.71652pt}{if
$v=v_{\mathrm{bot}}$ and not all objects\\\ in $\mathcal{O}(v,w)$ intersect
$v_{\mathrm{bot}}w$}\\\\[8.53581pt]
\mathrm{area}(\Delta(v_{\mathrm{bot}},v,w))+\min\limits_{u\in
V(v,w)}A[u,v]&\mbox{otherwise.}\end{cases}$

Putting everything together, we can prove Theorem 1.2.

######  Proof 4.2.

First, we compute the approximately optimal intersecting polygon with at most
$8$ vertices in $O(n^{17}\log(1/\varepsilon))$ time by Theorem 4.5, see below.
The set $\mathcal{G}$ of $O(n^{10})$ candidate grids can be computed in
$O(n^{10})$ time. Each grid $G\in\mathcal{G}$ has $O(1/\varepsilon^{6})$
vertices, among which we guess the vertex $v_{\mathrm{bot}}$ in
$O(1/\varepsilon^{6})$ time.

For each guess we run the dynamic programming, whose table has
$O(1/\varepsilon^{12})$ entries $A[u,v]$. Again the most time-consuming part
of computing a table entry is in the third case of Lemma 4.1: for each of the
$O(1/\varepsilon^{6})$ points $u\in V(v,w)$ we check if all objects in
$\mathcal{O}(v,w)\setminus\mathcal{O}(u,v)$ intersect
$\Delta(v_{\mathrm{bot}},v,w)$. Thus computing $A[v,w]$ takes
$O(n/\varepsilon^{6})$ time, and the dynamic program takes
$O(n/\varepsilon^{18})$ time. This part of the algorithm therefore takes
$O(n^{10})\cdot O(1/\varepsilon^{6})\cdot
O(n/\varepsilon^{18})=O(n^{11}/\varepsilon^{24})$ time.

###  4.1 Approximating the minimum area polygon of constantly many vertices

Here we will show how that one can compute an approximate minimum-area
intersecting polygon with $k\leqslant 8$ vertices; we will run this algorithm
for each $k=2,3,\dots,8$. If $k=2$, then the optimum is a degenerate polygon
(a segment) of area $0$. Since the length of the segment is irrelevant, it is
in fact enough to check if there is a line that intersects all input objects.
If there is such a line, then it can be rotated until it passes through two
vertices of input objects without affecting feasibility. Thus, in $O(n^{2})$
time, we can enumerate all pairs of vertices, and for each pair we can check
in $O(n)$ time whether the line through them intersects all objects.
Consequently, in $O(n^{3})$ time we can decide if there is a feasible solution
with $k=2$ (and $\mbox{{\sc opt}}=0$).

Assume now that $\mbox{{\sc opt}}>0$ and $3\leqslant k\leqslant 8$. Notice
that any intersecting polygon that has a vertex outside the union of the
boundaries of $\mathcal{O}$ cannot be optimal, as such a vertex can be moved
to a boundary while maintaining feasibility and decreasing the area of the
intersecting polygon. We begin our algorithm by guessing the $k$ input polygon
sides on which these vertices lie. These sides can be written as
$p_{i}+\lambda_{i}s_{i}$, where $p_{i}$ is an arbitrary point on the polygon
side, $s_{i}$ is a unit vector parallel to the side, and $\lambda_{i}$ is a
real number from some interval (where the interval may be unbounded on either
side). We are then looking for a polygon with vertices of the form
$v_{i}=p_{i}+\lambda_{i}s_{i}$ for each $i\in[k]$.

Next, we can express the feasibility of the solution using constant-degree
polynomial inequalities over the variables $\lambda_{i}$. Indeed, for a fixed
cyclic ordering of the vertices along the boundary of the optimum polygon, the
convexity can be expressed by the fact that consecutive triplets have the same
orientation. Applied for all cyclic orderings $\xi$, we get

$\bigvee_{\begin{subarray}{c}\xi:[k]\rightarrow[k]\\\ \text{ cyclic order
}\end{subarray}}\bigwedge_{j\in[k]}\quad\Big{(}\mathrm{det}(v_{\xi(j)}-v_{\xi(j+1)},\;v_{\xi(j)}-v_{\xi(j+2)})>0\Big{)},$

where indices are modulo $k$ and $\mathrm{det}(a,b)$ is the determinant of the
$2\times 2$ matrix with columns $a$ and $b$.

In order to check feasibility for each convex polygon $\mathcal{O}$, we can
write a Boolean expression of $O(n)$ constraints expressing that for each
object $o\in\mathcal{O}$ there is a side of $o$ and a side of the intersecting
polygon that intersect. These constraints are again expressible as the signs
of $2\times 2$ determinants involving the vertices of some $o\in\mathcal{O}$
and of the intersecting polygon.

Finally, for a target real value $\mu>0$, we can express that the area of the
intersecting polygon is at most $\mu$: the area of a polygon can be expressed
as the sum of signed areas of the triangles formed by its sides and a
designated vertex. The area is therefore a degree-2 polynomial of the
variables $\lambda_{i}$.

Thus, we can express that there is a size-$k$ solution with a Boolean formula
of $O(n)$ polynomial inequalities of degree $2$, where the variables
$\lambda_{1},\dots,\lambda_{k}$ are existentially quantified. We get a Boolean
expression $\Phi_{\mu}$ of $O(n)$ polynomial inequalities of degree $2$ that
has $k\leqslant 8$ existentially quantified variables (as we can reuse the
variables for different values of $k$). Formula $\Phi$ is true if and only if
there is a solution on $k$ vertices of area at most $\mu$.

Basu et al. [3] provide an algorithm to decide the truth of a formula with $t$
existentially quantified variables that has $s$ polynomial inequalities of
degree at most $d$ with $s^{t+1}d^{O(t)}$ time, which is $O(n^{9})$ time in
case of $\Phi_{\mu}$. We can therefore use a binary search strategy to find a
value $\mu$ such that $\Phi_{\mu/(1+\varepsilon)}$ is false and $\Phi_{\mu}$
is true. One can observe that it is sufficient to search among the values
$\mu=(1+\varepsilon)^{z}$ where $z$ is an integer. In order to ensure that the
strategy can begin and it terminates, it is necessary that we have an upper
bound and a positive lower bound for opt.

Recall that our input is a set of points with $c\log n$-bit coordinates for
some constant $c$. We can imagine that these points are grid points from a
grid of size $n^{c}\times n^{c}$, and we fix the unit to be the side length of
a grid cell. Observe that $\mbox{{\sc opt}}\leqslant n^{2c}$ as the
circumscribed square of the grid is a valid solution. We will now work towards
a lower bound.

######  Lemma 4.3.

Let $C_{\mathrm{opt}}$ be a minimum area convex overlapping polygon for a set
$\mathcal{O}$ of convex polygons. If $\mathrm{area}(C_{\mathrm{opt}})>0$ then
$\mathrm{area}(C_{\mathrm{opt}})\geqslant\Omega(\frac{1}{n^{8c}})$.

######  Proof 4.4.

If $\mathrm{area}(C_{\mathrm{opt}})>0$, then $C_{\mathrm{opt}}$ has at least
$3$ edges and thus contains at least two vertices from $X$ by Lemma 2.2. Let
$u,v\in X\cap\partial C_{\mathrm{opt}}$ be such points. Notice that $\partial
C_{\mathrm{opt}}$ also has a vertex $w$ on some edge $e$ of an input polygon
that is not incident to $a$ or $b$. We claim that the triangle $uvw$ has sides
of length at least $1/n^{O(n)}$. Notice that this is sufficient to show the
lemma, as it implies that the triangle has area $1/n^{O(n)}$, and since the
triangle is contained in $C_{\mathrm{opt}}$, the same area lower bound holds
also for $C_{\mathrm{opt}}$.

Consider first the point $u$. It is either an input point (and thus it has
integer coordinates) or it is the intersection of two polygon edges, each of
which are defined as the line through two points form the integer $n^{c}\times
n^{c}$ grid. Therefore, $u$ is the intersection of the lines
$a_{1}x+b_{1}y=c_{1}$ and $a_{2}x+b_{2}y=c_{1}$, where
$a_{i},b_{i},c_{i}\;(i=1,2)$ are integers between $0$ and $n^{c}$. Elementary
geometry yields that the first coordinate of the intersection can be written
in the form $p_{u}/q_{u}$, where $p_{u}$ and $q_{u}$ are quadratic expressions
of $a_{i},b_{i},c_{i}\;(i=1,2)$ with coefficients $\pm 1$. We also write the
first coordinate of $v$ as $p_{v}/q_{v}$. Thus if the first coordinate of $u$
and $v$ are different, then they differ by at least $1/q_{u}q_{v}\geqslant
1/O(n^{4c})$, so applying the same argument to the second coordinates, we get
$\mathrm{dist}(u,v)\geqslant\min(|u_{x}-v_{x}|,|u_{y},v_{y}|)\geqslant\Omega(1/n^{4c})$.

Similarly, the minimum distance of $u$ to the line defined by the edge $e$ is
an expression of the form $p_{e}/q_{e}$ where $q$ is a degree four polynomial
with constant coefficients over the coordinates of $u$ and the coordinates of
the points defining $e$. Thus we have that
$\mathrm{dist}(u,w)\geqslant\mathrm{dist}(u,e)\geqslant\Omega(1/n^{4c})$. An
analogous argument works for the distance of $v$ and $w$, hence the area of
the triangle $uvw$ is at least $\Omega(1/n^{8c})$.

######  Theorem 4.5.

Let $\mathcal{O}$ be a set of convex polygons of total complexity $n$ in
$\mathbb{R}^{2}$ and let $\varepsilon>0$. Suppose that the minimum area convex
intersecting polygon of $\mathcal{O}$ has area opt. Then given $\varepsilon$
and $\mathcal{O}$, we can compute in $O(n^{17}\log(1/\varepsilon))$ time a
convex intersecting polygon $C$ of $\mathcal{O}$ where
$\mathrm{area}(C)\leqslant(1+\varepsilon)\mbox{{\sc opt}}$.

######  Proof 4.6.

Recall that we guess the $k\leqslant 8$ input polygon sides, giving $O(n^{k})$
options to start with. For a fixed choice of $k$ sides, let $\Phi_{\mu}$ be
the formula described above with target value $\mu$. The truth of the formula
for any $\mu>0$ can be decided in time $n^{O(1)}$. By our upper bound and by
Lemma 4.3 the range of possible values for opt is between $\Omega(1/n^{8c})$
and $n^{2c}$, thus the number of distinct values to consider is
$O(\log_{1+\varepsilon}\frac{n^{2c}}{1/n^{8c}})=O(\frac{\log
n}{\varepsilon})$. Doing binary search over this many values leads to
$O(\log\frac{\log n}{\varepsilon})=O(\log\log n+\log(1/\varepsilon))$
evaluations of the formula $\Phi$, which by Basu et al. [3] needs $O(n^{9})$
time, resulting in an overall running time of $O(n^{8})\cdot
O(n^{9}\log(1/\varepsilon))=O(n^{17}\log(1/\varepsilon))$.

##  5 An exact algorithm for the minimum-perimeter intersecting polygon of
segments

We describe an exact algorithm to compute a minimum-perimeter intersecting
object for a set $\mathcal{O}$ of line segments111Although we describe our
algorithm for non-degenerate segments, all our arguments also work if some (or
all) of the segments are in fact lines, rays, or even points. in the plane.
Consider an optimal solution $C_{\mathrm{opt}}$, and let $Y$ be the set of all
endpoints of the segments in $\mathcal{O}$. The exact algorithm is based on
two subroutines for the following two problems. As before, whenever we talk
about intersecting polygons, we implicitly require them to be convex. Figure 4
illustrates the polygons computed by these subroutines.

Figure 4: (i) Subroutine I computes a minimum perimeter intersecting polygon
whose vertices are not segment endpoints. (ii) Subroutine II computes a
polygon with fixed edge $uv$ for some (sub)set of segments. With the exception
of $u$ and $v$, the polygon’s vertices are not allowed to be segment
endpoints.

  * •

_Subroutine I_ : If $\mathcal{O}$ admits a minimum-perimeter intersecting
polygon with none of its vertices being in $Y$, then compute such a polygon.
Otherwise compute a feasible intersecting polygon, or report $+\infty$.

  * •

_Subroutine II_ : Given two points $u,v\in\mathbb{R}^{2}$ and a subset
$\mathcal{O}^{\prime}\subseteq\mathcal{O}$, decide if $\mathcal{O}^{\prime}$
admits a minimum-perimeter intersecting polygon that has $uv$ as one of its
edges and none of whose other vertices belongs to $Y$ and, if so, compute a
minimum-perimeter such intersecting polygon. If no such minimum-perimeter
intersecting polygon exists, report $+\infty$. Note that we allow $u=v$, in
which case the edge $uv$ degenerates to a point.

###  5.1 Subroutines I and II

The goal of this subsection is to show the following theorem.

######  Theorem 5.1.

There exist exact algorithms for _Subroutine I_ and _Subroutine II_ that run
in time $O(n^{6}\log n)$ and $O(n^{3}\log n)$, respectively.

We want to establish that a portion of a minimum-perimeter polygon $\Gamma$
that does not contain any segment endpoints, is tractable in the sense that we
can compute it with a black-box application of [5]. More specifically, we will
prove Theorem 5.1 by invoking an algorithm for the Touring Polygons Problem
[5] as a black box. For completeness we repeat the relevant definitions and
results from [5]. We start by defining the Touring Polygons Problem (TPP).
Note that in [5] a more general version is considered that requires the
solution to remain within a fenced area, but we are only interested in the
"unfenced" special case which slightly simplifies notation.

######  Definition 5.2 ((unfenced) Touring Polygons Problem (TPP)[5]).

In the Touring Polygons Problem (TPP) we are given a sequence of convex
polygons $P_{1},P_{2}\dots P_{k}$, a starting point $s=P_{0}$, and an ending
point $t=P_{k+1}$. We say that a path $\pi$ visits $P_{i}$, if $\pi\cap
P_{i}\neq\varnothing$, and that $\pi$ visits the polygon sequence $P_{1},\dots
P_{k}$ if there exist points $q_{i}\in P_{i}$ such that the $q_{i}$’s appear
in order of index along $\pi$. We seek to output the shortest path $\pi$
starting at $s$ and visiting the sequence of input polygons before finishing
at $t$.

Let $n$ be the total complexity of the $k$ polygons input to TPP. Then:

######  Theorem 5.3 (Theorem $2$ in [5]).

The TPP for arbitrary convex polygons $P_{i}$ can be solved in time
$O(nk^{2}\log n)$, using $O(kn)$ space.

Note that for segments and half-planes $k=O(n)$, and therefore TPP can be
solved in $O(n^{3}\log n)$ time and quadratic space.

An important property of an optimal solution to TPP is _uniqueness_ :

######  Lemma 5.4 (Lemma $8$ in [5] (unfenced)).

For any points $s,t\in\mathbb{R}^{2}$ there is a unique shortest path from $s$
to $t$ that visits the polygons $P_{1},\dots P_{k}$ in order.

#### Reduction

We define a set of half-planes and an ordering on them, such that the optimum
tour of the half-planes that respects the ordering gives a minimum
intersecting polygon of the segments. In what follows, we will deal with a
portion of the boundary of a minimum intersecting polygon (denoted by
$\Gamma$), that is, a convex chain from some point $u$ to some point $v$. For
the sake of simplicity, we rotate the polygon so that $u,v$ are on the
$x$-axis, and the chain $\Gamma$ lies in the upper half-plane. Let $C(\Gamma)$
denote the polygon given by $\Gamma$ and the segment $uv$. The set of line
segments to be intersected by $C(\Gamma)$ will be denoted by $\mathcal{O}$.

Let us thus fix two points $u,v$ on the $x$-axis, and let $\mathcal{O}$ be a
set of $n$ segments. The _half-plane of $o\in\mathcal{O}$ with respect to
$u,v$_ is the (closed) half-plane defined by $\mathrm{line}(o)$ that (i) does
not contain $u$ (see Figure 5), or (ii) if $u\in\mathrm{line}(o)$, then it is
the half-plane containing $v$, or (iii) if $\mathrm{line}(o)=\overline{uv}$
then it is the upper half-plane defined by the $x$-axis. We sort all these
half-planes of segments according to the direction of their normal vectors in
clockwise order, where the ordering of directions is set to start with
$(0,-1)$. Let $\vec{n_{i}}$ be the normal vector of half-plane $H_{i}$, and
let $\vec{n_{0}}=(0,-1)$ denote the normal of the half-plane $y\leqslant 0$.
Let $o_{i}$ be the segment that was used to define $H_{i}$. Finally, let
$\mathcal{H}$ denote the set of half-planes $H_{i}$ for $i\geqslant 1$.

Figure 5: Illustration for case (i).

We first show that there exists a convex chain $\Gamma$ from $u$ to $v$ that
visits all $H_{i}$ in order, i.e., there exist $t_{i}\in H_{i}$ such that
$\Gamma$ visits the $t_{i}$’s in order. (In fact, we show the stronger
statement that this holds for any convex chain from $u$ to $v$ that visits all
half-planes.)

######  Lemma 5.5.

Fix the points $u,v$ on the $x$-axis and let $o_{1},\dots,o_{n}$ be $n$ line
segments, with corresponding half-planes $H_{i}$ where indices follow the
ordering of the half-planes according to their normals as above. Consider a
clockwise-oriented convex chain $\Gamma$ from $u$ to $v$ in the half-plane
$y\geqslant 0$ that visits each half-plane $H_{i}(i=1,\dots,n)$. Then there
exist $n$ (not necessarily distinct) points $t_{i}\in H_{i}$, such that
$\Gamma$ visits the points $t_{i}$ in the order of their indices.

######  Proof 5.6.

For a fixed path $\Gamma$ with the previous properties, the points $t_{i}$
will be defined with an iterative procedure. Let $j$ be a variable index
initially set to one and establish a queue that contains all the half-planes
in the specified order. Then the definition of the $t_{i}$ points comes from
the following procedure:

Figure 6: Illustration of the procedure.

  1. 1.

Start from the point $u$ and follow the path $\Gamma$ until the first exit
from a half-plane of the queue; suppose that this happens at a point
$u^{\prime}$. Let $k$ be the largest index of a half-plane that is being
exited at $u^{\prime}$.

  2. 2.

Set $t_{j},\dots,t_{k}=u^{\prime}$.

  3. 3.

Set $j$ equal to $k+1$ and remove the half-planes with index less or equal to
$k$ from the queue. As long as the queue is not empty, repeat the first step
with $u=u^{\prime}$.

If the point $v$ is part of a half-plane $H_{k}$, then the path $\Gamma$ would
never exit $H_{k}$. Therefore, there will be an iteration of the previous
procedure, such that the path $\Gamma$ in the first step will meet the point
$v$, while the queue will not be empty. In this case, the procedure stops and
every remaining $t_{i}$ is set equal to $v$.

Assuming that the $t_{i}$ points exist, by the construction, the path $\Gamma$
visits them in the specified order. Therefore it is sufficient to show that
the points $t_{i}$ exist and that $t_{i}\in H_{i}$ for all $i$. Consider an
iteration and let $j$, $k$, $u$ and $u^{\prime}$ be the corresponding
variables of the first two steps of the iteration.

First, we show that for every $i:j\leqslant i\leqslant k$, it holds that
$t_{i}\in H_{i}$. Suppose to the contrary that $t_{i}=u^{\prime}\notin H_{i}$.
Since $\Gamma$ is convex and has clockwise orientation, the rest of $\Gamma$
remains in the interior of the cone defined by the segment $u^{\prime}v$ and
$\partial H_{k}$ (see Figure 7), which is disjoint from $H_{i}$ (since (i)
$i\leq k$, thus
$\sphericalangle(n_{0},n_{i})\leq\sphericalangle(n_{0},n_{k})$, and (ii)
$u^{\prime}\not\in H_{i}$). Therefore $\Gamma$ cannot intersect $H_{i}$ after
leaving $u^{\prime}$. Hence from the feasibility of $\Gamma$, the path must
exit $H_{i}$ before it exits $H_{k}$, but this contradicts the definition of
$u^{\prime}$.

Figure 7: The first exit from a half-plane is not at point $u^{\prime}$. This
is a contradiction.

Next, we show that every half-plane of index larger than $k$ will be visited
by $\Gamma$ after the point $u^{\prime}$. Suppose to the contrary that there
exists a half-plane $H_{i}$ with $i>k$ which is not visited by $\Gamma$ after
the point $u^{\prime}$. In particular, we have that $v\not\in H_{i}$. From the
feasibility of $\Gamma$, we can conclude that the path $\Gamma$ has exited
from $H_{i}$ before or exactly at $u^{\prime}$, but this contradicts the
definition of $u^{\prime}$ and $k$. This concludes the proof.

If we run the TPP-algorithm from [5] on $u,\mathcal{H},v$ (where $\mathcal{H}$
is ordered by the order specified above), then we obtain as output the
shortest path $P$ from $u$ to $v$ that visits all half-planes in the given
order. It is still possible though for the polygon defined by $P$ and $uv$ to
not overlap $o_{i}$ (although $P$ visits $H_{i}$). However we claim that if
the optimal solution $\Gamma$ does not go through any segment-endpoint then
$P$ is not only feasible but also optimal for _Subroutine I_ on this input. To
show this, we need the following lemma, which shows that the convex
combination of two different-length paths with the same ordering must be
strictly shorter than the longest of the two paths.

######  Lemma 5.7.

Let
$\Gamma_{0}=\\{p=a_{0},a_{1},\dots,a_{n}=q\\},\;\Gamma_{1}=\\{p=b_{0},b_{1},\dots,b_{n}=q\\}$
be two paths such that $|\Gamma_{0}|<|\Gamma_{1}|$. For a fixed $\lambda$,
construct a path $\Gamma_{\lambda}=\\{p=c_{0},c_{1},\dots,c_{n}=q\\}$, where
$c_{i}=\lambda\cdot b_{i}+(1-\lambda)\cdot a_{i}$. Then for every
$\lambda:0\leqslant\lambda<1$, it holds that
$|\Gamma_{\lambda}|<|\Gamma_{1}|$.

######  Proof 5.8.

We can bound $|\Gamma_{\lambda}|$ in the following way:

$\displaystyle|\Gamma_{\lambda}|$
$\displaystyle=\sum_{i=0}^{n-1}|c_{i+1}-c_{i}|$
$\displaystyle=\sum_{i=0}^{n-1}|\lambda b_{i+1}+(1-\lambda)a_{i+1}-\lambda
b_{i}-(1-\lambda)a_{i}|$
$\displaystyle=\sum_{i=0}^{n-1}|\lambda(b_{i+1}-b_{i})+(1-\lambda)(a_{i+1}-a_{i})|$
$\displaystyle\leqslant\sum_{i=0}^{n-1}\Big{(}|\lambda(b_{i+1}-b_{i})|+|(1-\lambda)(a_{i+1}-a_{i})|\Big{)}$
$\displaystyle=\lambda\sum_{i=0}^{n-1}|b_{i+1}-b_{i}|+(1-\lambda)\sum_{i=1}^{n-1}|a_{i+1}-a_{i}|.$
$\displaystyle=\lambda|\Gamma_{1}|+(1-\lambda)|\Gamma_{0}|$
$\displaystyle<|\Gamma_{1}|.$

The next lemma allows us to invoke the algorithm of [5] to compute a polygon
portion, assuming that the portion does not contain segment endpoints.

######  Lemma 5.9.

Let $C(\Gamma)$ be a minimum intersecting polygon for a set $\mathcal{O}$ of
segments. Let $\mathcal{H}$ be the set of half-planes corresponding to
$\mathcal{O}$, and let $\Gamma_{\mathcal{H}}$ be the shortest path from $u$ to
$v$ that visits all half-planes in $\mathcal{H}$ in the order defined by their
indices, i.e., there are points $t_{i}\in H_{i}$ so that
$\Gamma_{\mathcal{H}}$ goes through the points $t_{i}$ in the order of their
indices. Suppose that $\Gamma$ does not contain any of the endpoints of the
segments (with the possible exception of $u$ and $v$). Then
$\Gamma=\Gamma_{\mathcal{H}}$.

######  Proof 5.10.

By Lemma 5.5 and the convexity of $\Gamma$, there are $n$ points $a_{i}\in
H_{i}$ for $\Gamma$ such that the path $\Gamma$ visits them in the specified
order. We claim that there are no other vertices on $\Gamma$, that is, it can
be represented as the convex chain

$\Gamma=(u,a_{1},\dots,a_{n},v),\text{where }a_{i}\in H_{i}.\\\ $

Indeed, if $v$ is a vertex of $\Gamma$ that is not a visit point, then $v$
cannot be the only point where some $o_{i}$ is visited, so we can shorten
$\Gamma$ by shortcutting from the last point of $\bigcup_{i}o_{i}$ before $v$
to the first point of $\bigcup_{i}o_{i}$ after $v$ (in case $\Gamma$ and some
$o_{i}$ have a shared segment $s$ starting/ending at $v$, then we use the
starting/ending point of $s$ as the starting/ending point of the shortcut).

Since $\Gamma$ does not contain endpoints apart from $u$ and $v$, all of its
internal vertices are in the interior of some segment in $\mathcal{O}$ that is
tangent to $C(\Gamma)$ by a similar shortcutting argument. Notice that if
$\Gamma$ visits some segment $o_{i}$, that is tangent to $C(\Gamma)$ then
$H_{i}$ intersects $\Gamma$ only at this point; consequently, this is the only
location where the point $a_{i}$ could be located. To summarize, at each
vertex of $\Gamma$ there must be some segment $o_{i}$ whose half-plane $H_{i}$
can be visited only there, and therefore all vertices of $\Gamma$ are
contained in the sequence $(u,a_{1},\dots,a_{n},v)$.

By the definition of $\Gamma_{\mathcal{H}}$, it contains points
$u,b_{1},\dots,b_{n},v\;(b_{i}\in H_{i})$ in this order; we claim that it can
be represented as the chain

$\Gamma_{\mathcal{H}}=(u,b_{1},\dots,b_{n},v),\text{where }b_{i}\in H_{i}.$

This is easy to see: the chain $(u,b_{1},\dots,b_{n},v)$ visits all the half-
planes in the correct order and any tour containing these points in this
sequence cannot be shorter than this chain.

Continuing the proof, suppose that $\Gamma\neq\Gamma_{\mathcal{H}}$. The path
$\Gamma_{\mathcal{H}}$ is the shortest path visiting the polygons
$u,H_{1},\dots,H_{n},v$ in this order, so by Lemma 5.4, $\Gamma_{\mathcal{H}}$
is the unique such shortest path. The path $\Gamma$ is a different chain
visiting each of these polygons in the same order, therefore
$|\Gamma_{\mathcal{H}}|<|\Gamma|$. Since $\Gamma$ does not visit any endpoint
of the segments in $\mathcal{O}$, any $u\rightarrow v$ curve where each point
$a_{i}$ is moved by a small amount towards some other point in $H_{i}$ is also
feasible. In particular, it follows that there exists a small $0<\lambda<1$
such that the path

$\Gamma^{\prime}=\\{u,c_{1},\dots,c_{n},v\\}\text{, where }c_{i}=\lambda
a_{i}+(1-\lambda)b_{i}$

gives a feasible polygon $C(\Gamma^{\prime})$ for $\mathcal{O}$. By Lemma 5.7,
it holds that $|\Gamma^{\prime}|<|\Gamma|$, which contradicts the optimality
of $\Gamma$.

We are now ready to prove Theorem 5.1.

######  Proof 5.11 (Proof of Theorem 5.1).

First we provide an algorithm for _Subroutine I_. If the optimum intersecting
polygon’s boundary does not go through any segment endpoints, then we use
Lemma 5.9 for an arbitrary vertex $u$ of the optimum as a designated start-
and endpoint. It follows that the boundary of the minimum perimeter
intersecting polygon for $\mathcal{O}$ and the optimum tour of the half-planes
corresponding to $\mathcal{O}$ in the order defined by their normals is
identical.

To find this point $u$ we use the algorithm from [4]. The algorithm [4] is
designed for the so-called _watchman tour_ problem, but this is equivalent to
our setting, see [13] and the relevant discussion in [5]. The algorithm of [4]
computes $O(n^{3})$ candidate points (called _event points_ in the terminology
of [4]) in $O(n^{3})$ time, while providing the guarantee that the optimal
tour will go through at least one of them. By Theorem 5.3 for each of these
$O(n^{3})$ points a TPP solution can be computed in $O(n^{3}\log n)$ time.
Then for each TPP solution we can check if the corresponding polygon is convex
and intersects all the segments in $O(n^{2})$ time. In the end, we return the
minimum-perimeter feasible polygon found, or $+\infty$ if none of the
$O(n^{3})$ polygons are feasible. If the optimum polygon has no segment
endpoints as vertices, then the returned polygon is the optimum. The algorithm
takes $O(n^{3})\cdot(O(n^{3}\log n)+O(n^{2}))=O(n^{6}\log n)$, time, which
concludes the proof for _Subroutine I_.

With respect to _Subroutine II_ first note that if $u\neq v$, then all that is
required is a single call to the TPP algorithm with a running time of
$O(n^{3}\log n)$. Furthermore, if $u=v$, then Lemmas 5.5, 5.7 and 5.9 all
still work. Consequently, if the optimum tour of the complete set
$\mathcal{O}$ of segments contains only one segment endpoint $u$, then the
minimum intersecting polygon for the polygons $u,H_{1},\dots H_{n},u$ (which
is a single call to the TPP algorithm as well) is also optimal for
$\mathcal{O}$. Here Lemmas 5.4, 5.5, and 5.9 give a way to detect whether the
optimal polygon for a given set of segments and points $u,v$ is equal to the
TPP solution. Indeed, if the polygon corresponding to the TPP solution is
feasible (the corresponding polygon intersects all segments in $\mathcal{O}$)
and its vertices apart from $u,v$ are not from $Y$, then it must be the
optimum. Consequently, if the polygon given by the TPP solution is non-convex,
or if it fails to intersect some polygon, or if it contains a segment
endpoint, then we can return $+\infty$ as the cost of the respective tour. The
feasibility checks can be done in $O(n^{2})$ time, thus the dominant part of
the running time is $O(n^{3}\log n)$.

#### Setting the stage for the dynamic program.

With Subroutine I available, it remains to find the minimum-perimeter
intersecting polygon at least one of whose vertices is a point from $Y$. To
this end we will develop an algorithm that, for a given point
$p_{\mathrm{bot}}\in Y$, finds a minimum-perimeter intersecting polygon that
has $p_{\mathrm{bot}}$ as a vertex (if it exists). We will run this algorithm
for each choice of $p_{\mathrm{bot}}\in Y$. Note that when we do so, we may
ignore all segments that contain $p_{\mathrm{bot}}$, as they will intersect
any intersecting polygon with $p_{\mathrm{bot}}$ as a vertex.

Let $p_{\mathrm{bot}}\in Y$ be given. We first check if $\mathcal{O}$ admits
an intersecting polygon that has $p_{\mathrm{bot}}$ as a vertex. This is the
case if and only if there exists a half-plane with $p_{\mathrm{bot}}$ on its
boundary that overlaps all segments in $\mathcal{O}$. The existence of such a
half-plane can easily be tested in $O(n\log n)$ using a rotational sweep
around $p_{\mathrm{bot}}$. So from now on we assume that an intersecting
polygon exists that has $p_{\mathrm{bot}}$ as a vertex. Let $C_{\mathrm{opt}}$
be a minimum-perimeter such intersecting polygon. The boundary of
$C_{\mathrm{opt}}$ consists of chains that connect points from $Y$ and such
that the interior vertices of these chains are disjoint from $Y$. (If
$p_{\mathrm{bot}}$ is the only point from $Y$ that is a vertex of
$C_{\mathrm{opt}}$, then there is a single chain connecting $p_{\mathrm{bot}}$
to itself.) We will develop a dynamic-programming algorithm similar to the
algorithm from Section 3. The dynamic program will be based on the points in
$Y$ (instead of on grid points) and we will use Subroutine II to find the
chains connecting the points from $Y$ on $\partial C_{\mathrm{opt}}$. As we
will see, however, there are several challenges that we need to overcome to
adapt the dynamic program.

Observe that if we take three rays emanating from $p_{\mathrm{bot}}$ that are
at a 120-degree angle from each other, then at least one of them lies fully
outside $C_{\mathrm{opt}}$ (except for the starting point $p_{\mathrm{bot}}$).
Consider such a ray $\rho_{0}$, and assume without loss of generality that
$\rho_{0}$ is a horizontal ray pointing leftwards. Our goal is now to find a
minimum-perimeter intersecting polygon with $p_{\mathrm{bot}}$ as a vertex and
that is not intersected by $\rho_{0}$. As mentioned, we will do this with a
dynamic program similar to the one from Section 3. The point
$p_{\mathrm{bot}}$ will play the role of $v_{\mathrm{bot}}$—but note that
$p_{\mathrm{bot}}$ need not be the lexicographically smallest vertex of
$C_{\mathrm{opt}}$—and $Y\setminus\\{p_{\mathrm{bot}}\\}$ will play the role
of $V$. Hence, it is convenient to redefine $Y$ as
$Y\setminus\\{p_{\mathrm{bot}}\\}$ and
$Y^{+}:=Y\cup\\{p_{\mathrm{bot}},\overline{p}_{\mathrm{bot}}\\}$, where
$\overline{p}_{\mathrm{bot}}$ is a copy of $p_{\mathrm{bot}}$. We define a
(partial) angular order $\prec$ on $Y^{+}$, as before.

In Section 3, we knew that $v_{\mathrm{bot}}$ was the lexicographically
smallest vertex of $C(\sigma)$, and so we were looking for solution that lies
above the horizontal line through $v_{\mathrm{bot}}$. This was important to be
able to decide which objects should be intersected by a partial solution; see
Figure 3. In the current setting, however, the point $p_{\mathrm{bot}}$ need
not be the lexicographically smallest point. Hence, we also need to guess the
orientation of the line tangent to $C_{\mathrm{opt}}$ at $p_{\mathrm{bot}}$.
To this end, let $\psi(o_{i})$ be the angle over which we have to rotate
$\rho_{0}$ in clockwise direction to make it parallel to a given segment
$o_{i}\in\mathcal{O}$, and sort the set of (distinct) angles $\psi(o_{i})$ in
increasing order. Let $\Psi:=\\{\psi_{1},\psi_{2},\ldots\\}$, where
$\psi_{j}<\psi_{j+1}$ for all $1\leqslant j<|\Psi|$, denote this sorted set.
Define $\psi_{0}:=0$ and $\psi_{|\Psi|+1}=\pi$. The problem we now wish to
solve is

> Given a point $p_{\mathrm{bot}}$ and value $j$ with $0\leqslant
> j\leqslant|\Psi|$, find a minimum-perimeter intersecting polygon
> $C_{\mathrm{opt}}$ for $\mathcal{O}$ such that
>
>   * •
>
> $p_{\mathrm{bot}}$ is a vertex of $C_{\mathrm{opt}}$,
>
>   * •
>
> the horizontal ray $\rho_{0}$ going from $p_{\mathrm{bot}}$ to the left does
> not intersect $C_{\mathrm{opt}}$,
>
>   * •
>
> $C_{\mathrm{opt}}$ has a tangent line $\ell$ at $p_{\mathrm{bot}}$ such that
> the clockwise angle from $\rho_{0}$ to $\ell$ lies in the range
> $[\psi_{j},\psi_{j+1}]$.
>
>

#### The dynamic program.

We will now develop our dynamic program for the problem that we just stated,
for a given point $p_{\mathrm{bot}}\in Y$, a ray $\rho_{0}$, and range
$[\psi_{j},\psi_{j+1}]$; see Figure 8(i).

Figure 8: (i) The grey double wedge indicates the region containing the
tangent at $p_{\mathrm{bot}}$. (Note that then there must be more segments
than the blue and red segments that are shown. In particular, there must be
segments parallel to the lines delimiting the double wedge.) The blue segments
are in $\mathcal{O}(\rho_{0})^{+}$ so they must be intersected by
$C_{\mathrm{opt}}^{+}$, while the red segment is in
$\mathcal{O}(\rho_{0})^{-}$ and must be intersected by $C_{\mathrm{opt}}^{-}$.
(ii) The definition of $\psi_{w}(o_{i})$.

Let $\mathcal{O}(\rho_{0})\subseteq\mathcal{O}$ denote the set of segments
that intersect the ray $\rho_{0}$, and let $\ell_{0}$ be the line containing
$\rho_{0}$. The line $\ell_{0}$ may split the optimal solution
$C_{\mathrm{opt}}$ into two parts: a part $C_{\mathrm{opt}}^{+}$ above
$\ell_{0}$ and a part $C_{\mathrm{opt}}^{-}$ below $\ell_{0}$. Let
$\psi(o_{i})$ denote the angle over which we have to rotate $\rho_{0}$ in
clockwise direction until it becomes parallel to $o_{i}$. Since we have fixed
the range of the tangent at $p_{\mathrm{bot}}$ to lie in the range
$[\psi_{j},\psi_{j+1}]$, we can split $\mathcal{O}(\rho_{0})$ into two
subsets,
$\mathcal{O}(\rho_{0})^{+}:=\\{o_{i}\in\mathcal{O}(\rho_{0}):\psi(o_{i})\geqslant\psi_{j+1}\\}$
and
$\mathcal{O}(\rho_{0})^{-}:=\\{o_{i}\in\mathcal{O}(\rho_{0}):\psi(o_{i})\leqslant\psi_{j}\\}$.

Note that
$\mathcal{O}(\rho_{0})=\mathcal{O}(\rho_{0})^{+}\cup\mathcal{O}(\rho_{0})^{-}$,
because $\psi_{j}$ and $\psi_{j+1}$ are consecutive angles in $\Psi$. Because
the orientation of the tangent at $p_{\mathrm{bot}}$ lies in the range
$[\psi_{j},\psi_{j+1}]$, we know that the segments in
$\mathcal{O}(\rho_{0})^{+}$ must be intersected by $C_{\mathrm{opt}}^{+}$,
while the segments in $\mathcal{O}(\rho_{0})^{-}$ must be intersected by
$C_{\mathrm{opt}}^{-}$; see Figure 8(i). Intuitively, the segments in
$\mathcal{O}(\rho_{0})^{+}$ must be intersected by “the initial part” of
$C_{\mathrm{opt}}$, while the segments in $\mathcal{O}(\rho_{0})^{-}$ are
intersected by “the later part”. We will use this when we define the
subproblems in our dynamic program.

In Section 3 we defined subproblems for pairs of grid points $v,w$. The goal
of such a subproblem was to find the minimum-length convex chain $\Gamma$ such
that $C(\Gamma)$ intersects a certain subset $\mathcal{O}(v,w)$ and whose last
edge is $vw$. The fact that we knew the last edge $vw$ was crucial to define
the set $\mathcal{O}(v,w)$, since the slope of $vw$ determined which objects
should be intersected by $C(\Gamma)$. In the current setting this does not
work: we could define a subproblem for pairs $v,w\in Y$, but “consecutive”
vertices $v,w$ from $Y$ along $\Gamma$ are now connected by a polyline
$Z_{vw}$ whose inner vertices are disjoint from $Y$. The difficulty is that
the polyline $Z_{vw}$ depends on the segments that need to be intersected by
$C(\Gamma)$. Hence, there is a cyclic dependency between the set of segments
to be intersected by $C(\Gamma)$ (which depends on the slope of $zw$, where
$z$ is the vertex of $Z_{vw}$ preceding $w$) and the vertex $z$ (which depends
on the segments that need to be intersected by $C(\Gamma)$). We overcome this
problem as follows.

Similarly to the previous section, we call a polyline $\Gamma$ from
$p_{\mathrm{bot}}$ to some point $v\in Y$ a _convex chain_ if, together with
the line segment $vp_{\mathrm{bot}}$, it forms a convex polygon. We denote
this polygon by $C(\Gamma)$. Consider a convex chain $\Gamma_{w}$ ending in a
point $w\in Y$. Let $\rho(w)$ denote the ray from $p_{\mathrm{bot}}$ through
$w$ and let $\rho^{*}(w)$ be the part of this ray starting at $w$. Let
$\mathcal{O}(w)$ be the set of input segments that intersect $\rho^{*}(w)$. Of
those segments, $C(\Gamma_{w})$ must intersect the ones such that the line
$\ell(o_{i})$ containing222Since the input objects are now segments, the
tangent line $\ell_{w}(o_{i})$ is just the line containing $o_{i}$. the
segment $o_{i}$ intersects the half-line containing $zw$ and ending at $w$,
where $z$ is the (unknown) vertex preceding $w$. For a segment
$o_{i}\in\mathcal{O}(w)$, let $\psi_{w}(o_{i})$ be the angle over which we
have to rotate $\rho(w)$ in clockwise direction to make it parallel to
$o_{i}$; see Figure 8(ii). Let $\Psi(w)=\\{\psi_{1},\psi_{2},\ldots\\}$, for
all $1\leqslant j<|\Psi(w)|$, be the sorted set of (distinct) angles
$\psi_{w}(o_{i})$ defined by the segments in $\mathcal{O}(w)$. For an index
$j$ with $1\leqslant j\leqslant|\Psi(w)|$, define
$\mathcal{O}(w,j):=\\{o_{i}\in\mathcal{O}(w):\psi_{w}(o_{i})\leqslant\psi_{j}\\}$,
and define $\mathcal{O}(w,0)=\varnothing$. We call $\mathcal{O}(w,j)$ a
_prefix set_. The key observation is that $C(\Gamma_{w})$ must intersect the
segments from some prefix set $\mathcal{O}(w,j)$, where $j$ depends on the
unknown vertex $z$ preceding $w$. So our dynamic program will try all possible
prefix sets $\mathcal{O}(w,j)$, and make sure that subproblems are combined in
a consistent manner.

We now have everything in place to describe our dynamic-programming table. It
consists of entries $A[w,j]$, where $w$ ranges over all points in $Y$, and $j$
ranges over all values for which $\mathcal{O}(w,j)$ is defined. For
convenience add two special entries, $A[p_{\mathrm{bot}},0]$ and
$A[\overline{p}_{\mathrm{bot}},0]$; the former will serve as the base case,
and the latter will contain (the value of) the final solution. Note that these
are the only ones for $p_{\mathrm{bot}}$ and $\overline{p}_{\mathrm{bot}}$,
and that we have at most $|Y|\cdot n=O(n^{2})$ entries. We define the set
$\mathcal{O}^{*}(w,j)$ of segments to be covered in a subproblem.

> For a point $w\in Y$, the set $\mathcal{O}^{*}(w,j)$ consists of the
> segments $o_{i}\in\mathcal{O}$ that satisfy one of the following conditions:
>

>>   1. (i)

>>

>> $o_{i}$ intersects the clockwise wedge from $\rho_{0}$ to $\rho(w)$—note
that this wedge need not be convex—but not $\rho(w)$ itself, and
$o_{i}\not\in\mathcal{O}^{-}(\rho_{0})$; or

>>

>>   2. (ii)

>>

>> $o_{i}$ intersects $p_{\mathrm{bot}}w$; or

>>

>>   3. (iii)

>>

>> $o_{i}\in\mathcal{O}(w,j)$.

>>

>>

>
> Furthermore, $\mathcal{O}^{*}(p_{\mathrm{bot}},0):=\varnothing$ and
> $\mathcal{O}^{*}(\overline{p}_{\mathrm{bot}},0):=\mathcal{O}$.

We would like now to define $A[w,j]$ to be the minimum length of a convex
chain $\Gamma$ from $p_{\mathrm{bot}}$ to $w$ such that all objects in
$\mathcal{O}^{*}(w,j)$ intersect $C(\Gamma)$. There is, however, a
technicality to address: the minimum-perimeter polygon that intersects all
segments from $\mathcal{O}$ need not be convex when we require it to have
$p_{\mathrm{bot}}$ as a vertex. Such a non-convex polygon cannot be the final
solution—if the optimum for a given choice of $p_{\mathrm{bot}}$ is non-
convex, then $p_{\mathrm{bot}}$ was not the correct choice—but it makes a
clean definition of our subproblems awkward. Therefore, instead of first
defining the subproblems and then giving the recursive formula, we will
immediately give the recursive formula and then prove that it computes what we
want.

For two points $v,w\in Y^{+}$ (where
$Y^{+}=Y\cup\\{\overline{p}_{\mathrm{bot}}\\}$) with $v\prec w$ and a set
$\mathcal{O}^{\prime}\subseteq\mathcal{O}$, let $L(v,w,\mathcal{O}^{\prime})$
be the minimum length of a convex chain $\Gamma$ from $v$ to $w$ such that the
convex polygon defined by $\Gamma$ and $vw$ is an intersecting set for
$\mathcal{O}^{\prime}$ and all inner vertices of $\Gamma$ are disjoint from
$Y$. Recall that we can compute $L(v,w,\mathcal{O}^{\prime})$ using subroutine
II. As before, let $\Delta(p_{\mathrm{bot}},v,w)$ denote the triangle with
vertices $p_{\mathrm{bot}},v,w$.

######  Definition 5.12.

Let $w\in Y^{+}$ and $j$ be a value for which $\mathcal{O}[w,j]$ is defined.
Thus $0\leqslant j\leqslant|\Psi(w)|$, where we set $|\Psi(w)|:=0$ for
$w\in\\{p_{\mathrm{bot}},\overline{p}_{\mathrm{bot}}\\}$. For $v\prec w$ and
$0\leqslant j^{\prime}\leqslant|\Psi(v)|$, let

$\mathcal{O}^{*}(w,j,v,j^{\prime}):=\mathcal{O}^{*}(w,j)\ \setminus\
\Big{(}\mathcal{O}^{*}(v,j^{\prime})\cup\\{o_{i}\in\mathcal{O}:o_{i}\mbox{
intersects }\Delta(p_{\mathrm{bot}},v,w)\\}\Big{)}$

and define

$A[w,j]\ :=\ \left\\{\begin{array}[]{ll}\hskip 19.91692pt0&\mbox{if
$w=p_{\mathrm{bot}}$}\\\ \min\limits_{\begin{subarray}{c}v\prec w\\\
0\leqslant
j^{\prime}\leqslant|\Psi(v)|\end{subarray}}L(v,w,\mathcal{O}^{*}(w,j,v,j^{\prime}))+A[v,j^{\prime}]&\mbox{otherwise.}\end{array}\right.$

The next lemma implies that the table entry $A[\overline{p}_{\mathrm{bot}},0]$
defined by this recursive formula gives us what we want. Part (a) implies that
$A[\overline{p}_{\mathrm{bot}},0]$ will never return a value that is too
small, while part (b) implies that for the correct choice of
$p_{\mathrm{bot}}$ and range of orientations for the tangent to
$C_{\mathrm{opt}}$ at $p_{\mathrm{bot}}$, the entry
$A[\overline{p}_{\mathrm{bot}},0]$ gives us (the value of) the optimal
solution.

######  Lemma 5.13.

Consider the table entry $A[\overline{p}_{\mathrm{bot}},0]$ defined by
Definition 5.12 for a given point $p_{\mathrm{bot}}$ and range
$[\psi_{i},\psi_{i+1}]$.

  1. (a)

There exists a convex intersecting polygon for $\mathcal{O}$ of perimeter at
most $A[\overline{p}_{\mathrm{bot}},0]$.

  2. (b)

If $p_{\mathrm{bot}}$ is a vertex of the minimum-perimeter convex intersecting
polygon $C_{\mathrm{opt}}$ for $\mathcal{O}$, and $\rho_{0}$ does not
intersect $C_{\mathrm{opt}}$, and there is a tangent line $\ell$ at
$p_{\mathrm{bot}}$ whose orientation is in the range $[\psi_{i},\psi_{i+1}]$,
then $\mathrm{per}(C_{\mathrm{opt}})=A[\overline{p}_{\mathrm{bot}},0]$.

######  Proof 5.14.

  1. (a)

We will prove by induction on $w$ (with respect to the order $\prec$) that for
any pair $(w,j)$ for which $A[w,j]$ is defined, there is a sequence
$\Xi(w,j)=v_{0},v_{1},\ldots,v_{k}$ of points from $Y$, where
$p_{\mathrm{bot}}=v_{0}\prec v_{1}\prec\cdots\prec v_{k}=w$, with the
following property: there are convex polygons $P_{1},\ldots,P_{k}$ such that

     * •

$v_{i-1}v_{i}$ is an edge of $P_{i}$,

     * •

$\sum_{i=1}^{k}\left(\mathrm{per}(P_{i})-|v_{i-1}v_{i}|\right)=A[w,j]$

     * •

$C(w,j):=\bigcup_{i=1}^{k}\left(P_{i}\cup\Delta(p_{\mathrm{bot}},v_{i-1},v_{i})\right)$
is an intersecting set for $\mathcal{O}^{*}(w,j)$.

Observe that the boundary length of $C(w,j)$ is at most
$A[w,j]+|w\overline{p}_{\mathrm{bot}}|$. Indeed, each edge $v_{i-1}v_{i}$ is
shared between the polygon $P_{i}$ and the triangle
$\Delta(p_{\mathrm{bot}},v_{i-1},v_{i})$, and so the contribution of the
polygons $P_{i}$ to the union boundary is at most
$\sum_{i=1}^{k}\left(\mathrm{per}(P_{i})-|v_{i-1}v_{i}|\right)=A[w,j]$. (At
most, because the $P_{i}$’s are not required to be disjoint.) Since the edges
$p_{\mathrm{bot}}v_{i}$ are shared between consecutive triangles
$\Delta(p_{\mathrm{bot}},v_{i-1},v_{i})$ and
$\Delta(p_{\mathrm{bot}},v_{i},v_{i+1})$, the contribution of triangles
$\Delta(p_{\mathrm{bot}},v_{i-1},v_{i})$ to the union boundary is at most
$|p_{\mathrm{bot}}v_{0}|+|p_{\mathrm{bot}}v_{k}|=|p_{\mathrm{bot}}w|$. Thus
the boundary length of $C(w,j)$ is at most
$A[w,j]+|w\overline{p}_{\mathrm{bot}}|$, as claimed. It follows that the
existence of the sequence $\Xi(\overline{p}_{\mathrm{bot}},0)$ implies part
(a) of the lemma, because
$\mathcal{O}^{*}(\overline{p}_{\mathrm{bot}},0)=\mathcal{O}$ and so the convex
hull of $C(\overline{p}_{\mathrm{bot}},0)$ is a convex intersecting set for
$\mathcal{O}$ of perimeter at most $A[\overline{p}_{\mathrm{bot}},0]$.

The base case is $(w,j)=(p_{\mathrm{bot}},0)$. Since
$\mathcal{O}^{*}(p_{\mathrm{bot}},0)=\varnothing$, the sequence consisting of
the single point $p_{\mathrm{bot}}$ trivially has the desired properties in
this case, with $C(p_{\mathrm{bot}},0)=\\{p_{\mathrm{bot}}\\}$.

Now consider a pair $(w,j)$ with $p_{\mathrm{bot}}\prec w$. Let $j^{\prime}$
be such that

$A[w,j]=L(v,w,\mathcal{O}^{*}(w,j,v,j^{\prime}))+A[v,j^{\prime}].$

By induction, there is a sequence $\Xi(v,j^{\prime})$ with the properties
stated above. We claim that the sequence $\Xi(w,j)$ we obtain by appending $w$
to $\Xi(v,j^{\prime})$ has the desired properties. Let
$\Xi(w,j)=v_{0},v_{1},\ldots,v_{k}$ and note that $v_{k-1}=v$ and $v_{k}=w$.
Take $P_{k}:=C(\Gamma)$, where $\Gamma$ is a minimum-length convex chain
$\Gamma$ from $v$ to $w$ such that $C(\Gamma)$ is an intersecting set for
$\mathcal{O}^{*}(w,j,v,j^{\prime})$. The induction hypothesis and the fact
that $A[w,j]=L(v,w,\mathcal{O}^{*}(w,j,v,j^{\prime}))+A[v,j^{\prime}]$ now
implies that $\Xi(w,j)$ has the first two properties. The third property
follows from the induction hypothesis and the definition of
$\mathcal{O}^{*}(w,j,v,j^{\prime})$.

  2. (b)

Since
$A[\overline{p}_{\mathrm{bot}},0]\geqslant\mathrm{per}(C_{\mathrm{opt}})$ by
part (a), it suffices to prove that
$A[\overline{p}_{\mathrm{bot}},0]\leqslant\mathrm{per}(C_{\mathrm{opt}})$. To
this end, let
$p_{\mathrm{bot}}=v_{0},v_{1},\ldots,v_{k}=\overline{p}_{\mathrm{bot}}$ be the
points from $Y$ on $\partial C_{\mathrm{opt}}$, in clockwise order. Let
$\Gamma_{i}$ denote the part of $\partial C_{\mathrm{opt}}$ from $v_{i-1}$ to
$v_{i}$ (in clockwise direction), and let $\Gamma_{\leqslant i}$ be the part
of $\partial C_{\mathrm{opt}}$ from $p_{\mathrm{bot}}$ to $v_{i}$. Let
$C_{\mathrm{opt}}^{(i)}$ denote the part of $C_{\mathrm{opt}}$ bounded by the
segment $v_{i-1}v_{i}$ and $\Gamma_{i}$; see Figure 9 for an illustration.

Figure 9: Illustration for the proof of Lemma 5.13.

For $1\leqslant i<k$, let $\ell_{i}$ be a line tangent to $C_{\mathrm{opt}}$
at $v_{i}$, and assume without loss of generality that $\ell_{i}$ is not
parallel to any segment in $\mathcal{O}$. Recall that $\Psi(v_{i})$ denotes
the sorted sequence of angles $\psi_{v_{i}}(o)$ defined by the segments in
$\mathcal{O}(v_{i})$, that is, by the segments intersecting the ray
$\rho^{*}(v_{i})$. Let $\psi_{i}^{*}$ be the angle over which we have to
rotate $\rho(v_{i})$ to make it parallel to $\ell_{i}$. Finally, let
$\Psi(v_{i}):=\langle\psi^{(i)}_{1},\psi^{(i)}_{2},\ldots\rangle$ and let
$j_{i}$ be the largest index such that $\psi^{(i)}_{j_{i}}<\psi_{i}^{*}$,
where we define $j_{0}=j_{k}=0$.

     * _Claim._ $C_{\mathrm{opt}}^{(i)}$ intersects all segments from $\mathcal{O}^{*}(v_{i},j_{i},v_{i-1},j_{i-1})$.

     * _Proof._ Partition $C_{\mathrm{opt}}$ into four pieces: $C_{\mathrm{opt}}^{(i)}$, the triangle $\Delta_{i}:=\Delta(p_{\mathrm{bot}},v_{i-1},v_{i})$, and two pieces denoted by $P$ and $P^{\prime}$, as depicted in Figure 9. Any segment $o\in\mathcal{O}$ intersects at least one of these pieces. We will show that if $o$ intersects $\Delta_{i}$ or $P$ or $P^{\prime}$, then $o\not\in\mathcal{O}^{*}(v_{i},j_{i},v_{i-1},j_{i-1})$, which implies the claim.

Note that for $i=1$ we have $v_{i-1}=p_{\mathrm{bot}}$, in which case
$\Delta_{i}$ degenerates to a line segment and $P=\varnothing$. Similarly, for
$i=k$ we have $v_{i}=\overline{p}_{\mathrm{bot}}$, in which case $\Delta_{i}$
degenerates to a line segment and $P^{\prime}=\varnothing$. Finally, when
$i=k=1$ we have $C_{\mathrm{opt}}^{(i)}=C_{\mathrm{opt}}$ and the claim
trivially holds.

       * –

If $o$ intersects $\Delta_{i}$ then
$o\not\in\mathcal{O}^{*}(v_{i},j_{i},v_{i-1},j_{i-1})$ by definition of
$\mathcal{O}^{*}(v_{i},j_{i},v_{i-1},j_{i-1})$.

       * –

Now suppose $o$ intersects $P$ but not $\Delta_{i}$.

If $o$ intersects $\rho(v_{i-1})$ then it must intersect $\rho^{*}(v_{i-1})$,
since we assumed $o$ does not intersect $\Delta_{i}$. But if $o$ intersects
$P$ and $\rho^{*}(v_{i-1})$, then $\psi_{v_{i-1}}(o)<\psi^{*}_{i-1}$ and so
$\psi_{v_{i-1}}(o)\leqslant\psi_{j_{i-1}}^{(i-1)}$. This means that
$o\in\mathcal{O}(v_{i-1},j_{i-1})\subseteq\mathcal{O}^{*}(v_{i-1},j_{i-1})$.
Hence, $o\not\in\mathcal{O}^{*}(v_{i},j_{i},v_{i-1},j_{i-1})$.

Now assume $o$ does not intersect $\rho(v_{i-1})$. Note that $o$ intersects
the wedge from $\rho_{0}$ to $\rho(v_{i-1})$, since $o$ intersects $P$. Then
the only reason for $o$ to not be in $o\in\mathcal{O}^{*}(v_{i-1},j_{i-1})$ is
if $o\in\mathcal{O}^{-}(\rho_{0})$. But then $o$ cannot intersect $P$. Hence,
$o\in\mathcal{O}^{*}(v_{i-1},j_{i-1})$ and so
$o\not\in\mathcal{O}^{*}(v_{i},j_{i},v_{i-1},j_{i-1})$.

       * –

Finally, suppose $o$ intersects $P^{\prime}$ but not $\Delta_{i}$. Note that
then $v_{i}\neq\overline{p}_{\mathrm{bot}}$, otherwise
$P^{\prime}=\varnothing$.

If $o$ intersects $\rho(v_{i})$ then it must intersect $\rho^{*}(v_{i})$,
since we assumed $o$ does not intersect $\Delta_{i}$. But if $o$ intersects
$P^{\prime}$ and $\rho^{*}(v_{i})$, then $\psi_{v_{i}}(o)>\psi^{*}_{i}$ and so
$\psi_{v_{i}}(o)>\psi_{j_{i}}^{(i)}$. This means that
$o\not\in\mathcal{O}(v_{i},j_{i})$. Since $o$ intersects $\rho^{*}(v_{i})$,
this means that $o\not\in\mathcal{O}^{*}(v_{i},j_{i})$ and hence, that
$o\not\in\mathcal{O}^{*}(v_{i},j_{i},v_{i-1},j_{i-1})$.

If $o$ does not intersect $\rho(v_{i})$, then either $o$ lies entirely in the
wedge from $\rho(v_{i})$ to $\rho_{0}$ or it intersects $\rho_{0}$. In the
former case $o$ clearly cannot satisfy any of the conditions to be in
$\mathcal{O}^{*}(v_{i},j_{i})$. In the latter case the fact that $o$
intersects $P^{\prime}$ implies that $o\in\mathcal{O}^{-}(\rho_{0})$, and so
$o\not\in\mathcal{O}^{*}(v_{i},j_{i})$. Hence,
$o\not\in\mathcal{O}^{*}(v_{i},j_{i},v_{i-1},j_{i-1})$.

$\lhd$

We now prove by induction on $i$ that
$A[v_{i},j_{i}]\leqslant\mathrm{length}(\Gamma_{\leqslant i})$ for all
$0\leqslant i\leqslant k$. Since
$(v_{k},j_{k})=(\overline{p}_{\mathrm{bot}},0)$ and
$\mathrm{length}(\Gamma_{\leqslant k})=\mathrm{per}(C_{\mathrm{opt}})$, this
will prove part (b).

The base case for the induction is when $i=0$. Then we have
$A[v_{0},j_{0}]=A[p_{\mathrm{bot}},0]=0=\mathrm{length}(\Gamma_{0})=\mathrm{length}(\Gamma_{\leqslant
0})$, since $\Gamma_{0}=\Gamma_{\leqslant 0}=\\{p_{\mathrm{bot}}\\}$. Now
suppose $i>0$. Then

$\begin{array}[]{lll}A[v_{i},j_{i}]&\leqslant&L(v_{i-1},v_{i},\mathcal{O}^{*}(v_{i},j_{i},v_{i-1},j_{i-1}))+A[v_{i-1},j_{i-1}]\mbox{
(by definition of $A[v_{i},j_{i}]$)}\\\
&\leqslant&\mathrm{length}(\Gamma_{i})+A[v_{i-1},j_{i-1}]\hfill\mbox{(by the
claim above)}\\\
&\leqslant&\mathrm{length}(\Gamma_{i})+\mathrm{length}(\Gamma_{\leqslant
i-1})\hfill\mbox{(by the induction hypothesis)}\\\
&=&\mathrm{length}(\Gamma_{\leqslant i}),\end{array}$

which finishes the proof.

#### Putting everything together.

Lemma 5.13 implies that after solving the dynamic programs for all choices of
$p_{\mathrm{bot}}$ and the range $[\psi_{i},\psi_{i+1}]$, we have found the
minimum perimeter intersecting set for $\mathcal{O}$. (Computing the
intersecting set itself, using the relevant dynamic-program table, is then
routine.) This leads to the proof of Theorem 1.3.

######  Proof 5.15 (Proof of Theorem 1.3.).

The number of dynamic programs solved is $O(|Y|\cdot n)=O(n^{2})$. The
dynamic-programming tables have $O(n^{2})$ entries. Computing an entry takes
$O(|Y|\cdot n)=O(n^{2})$ calls to Subroutine II, at $O(n^{3}\log n)$ time
each. The dynamic programs thus take $O(n^{2})\cdot O(n^{2})\cdot
O(n^{2})\cdot O(n^{3}\log n)=O(n^{9}\log n)$ time. If the optimal solution
does not go through any point of $Y$, then by Theorem 5.1 it will be found in
$O(n^{6}\log n)$ time. The optimum of these two algorithms is the global
optimum.

##  6 Conclusion

We gave fully polynomial time approximation schemes for the minimum perimeter
and minimum area convex intersecting polygon problems for convex polygons.
Additionally, we developed a polynomial-time algorithm for the minimum
perimeter problem of segments.

It is likely that the running times of our algorithms can be improved further.
One could also try to generalize the set of objects, for example, adapting the
minimum area algorithm to arbitrary convex objects. We propose the following
open questions for further study.

  * •

Is there a polynomial-time exact algorithm for the minimum area convex
intersecting polygon of segments?

  * •

Is there a polynomial-time exact algorithm for minimum perimeter or minimum
area convex intersecting polygon of convex polygons, or are these problems NP-
hard?

  * •

Is there a polynomial-time approximation scheme for the minimum volume or
minimum surface area convex intersecting polytope of convex polytopes in
$\mathbb{R}^{3}$? Can we at least approximate the diameter of the optimum
solution to these problems?

It would be especially interesting to see an NP-hardness proof for minimum
volume or surface area convex intersecting set of convex objects in higher
dimensions.

## References

  * [1] Antonios Antoniadis, Krzysztof Fleszar, Ruben Hoeksma, and Kevin Schewior.  A PTAS for Euclidean TSP with hyperplane neighborhoods.  ACM Trans. Algorithms, 16(3):38:1–38:16, 2020.
  * [2] Keith Ball.  Ellipsoids of maximal volume in convex bodies.  Geometriae Dedicata, 41(2):241–250, 1992.
  * [3] Saugata Basu, Richard Pollack, and Marie-Françoise Roy.  On the combinatorial and algebraic complexity of quantifier elimination.  J. ACM, 43(6):1002–1045, 1996.  doi:10.1145/235809.235813.
  * [4] 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.
  * [5] Moshe Dror, Alon Efrat, Anna Lubiw, and Joseph SB Mitchell.  Touring a sequence of polygons.  In STOC 2003: Proceedings of the thirty-fifth annual ACM symposium on Theory of computing, pages 473–482, 2003.
  * [6] Adrian Dumitrescu.  The traveling salesman problem for lines and rays in the plane.  Discrete Mathematics, Algorithms and Applications, 4(04):1250044, 2012.
  * [7] Adrian Dumitrescu and Minghui Jiang.  Minimum-perimeter intersecting polygons.  Algorithmica, 63(3):602–615, 2012.  doi:10.1007/s00453-011-9516-3.
  * [8] Ray A. Jarvis.  On the identification of the convex hull of a finite set of points in the plane.  Information processing letters, 2(1):18–21, 1973.
  * [9] Ahmad Javad, Ali Mohades, Mansoor Davoodi, and Farnaz Sheikhi.  Convex hull of imprecise points modeled by segments in the plane, 2010\.
  * [10] Yiyang Jia and Bo Jiang.  The minimum perimeter convex hull of a given set of disjoint segments.  In International Conference on Mechatronics and Intelligent Robotics, pages 308–318. Springer, 2017.
  * [11] Shunhua Jiang, Zhao Song, Omri Weinstein, and Hengjie Zhang.  A faster algorithm for solving general lps.  In STOC ’21: 53rd Annual ACM SIGACT Symposium on Theory of Computing 2021, pages 823–832. ACM, 2021.  doi:10.1145/3406325.3451058.
  * [12] Fritz John.  Extremum problems with inequalities as subsidiary conditions.  Courant Anniversary Volume, pages 187–204, 1948.
  * [13] Håkan Jonsson.  The traveling salesman problem for lines in the plane.  Inf. Process. Lett., 82(3):137–142, 2002.  doi:10.1016/S0020-0190(01)00259-9.
  * [14] Marc J. van Kreveld and Maarten Löffler.  Approximating largest convex hulls for imprecise points.  J. Discrete Algorithms, 6(4):583–594, 2008.  doi:10.1016/j.jda.2008.04.002.
  * [15] Maarten Löffler and Marc J. van Kreveld.  Largest and smallest convex hulls for imprecise points.  Algorithmica, 56(2):235–269, 2010.  doi:10.1007/s00453-008-9174-2.
  * [16] Franco P. Preparata and Se June Hong.  Convex hulls of finite sets of points in two and three dimensions.  Communications of the ACM, 20(2):87–93, 1977.
  * [17] Xuehou Tan.  The touring rays and related problems.  Theoretical Computer Science, 2021.
  * [18] Csaba D. Tóth, Joseph O’Rourke, and Jacob E Goodman.  Handbook of discrete and computational geometry.  CRC press, 2017.

##  Appendix A Visiting rays: on an algorithm of Tan

In this section we give a counterexample to a lemma of Tan [17] that is used
to establish his results on rays and segments. The paper uses the TSPN
framework: given a set of rays in the plane, we want to find the shortest
closed curve (a tour) intersecting all the rays.

In [17] the concept of a _pseudo-touring rays route_ is introduced, which is a
tour starting and ending at some fixed point $s$ that is allowed to not visit
some rays as long as their supporting line is crossed. The shortest pseudo-
tour for a starting point $s$ and ray set $R$ is denoted by POPT${}_{s}(R)$,
and the optimum tour visiting the rays and $s$ is denoted by OPT${}_{s}(R)$.
Let $\mathcal{H}$ be the convex hull of POPT${}_{s}(R)$ and the starting
points of the rays that are not visited by POPT${}_{s}(R)$. We note that [17]
shows that the optimal tour and pseudo-tour are unique. We prove the following
lemma, which is a contradiction to the statement of Lemma $6$ in [17]:

######  Lemma A.1.

There exists an input ray set $R$ such that the following hold: some ray $r$
is not visited by POPT${}_{s}(R)$, the starting point of $r$ is on
$\mathcal{H}$, and OPT${}_{s}(R)$ does not make a crossing contact with $r$.

######  Proof A.2.

We present an input instance consisting of a starting point $s=(0,-\epsilon)$,
for some $\epsilon<0.1$, and three rays defined as follows (see also Figure
10):

  * •

$r_{1}$ has $y=\frac{4}{5}x+\frac{4}{5}$ as supporting line, $o_{1}=(-1,0)$ as
starting point and the ray is pointing downwards.

  * •

$r_{2}$’s supporting line has the equation $y=1$, starting point
$o_{2}=(-1,1)$ and the ray is pointing towards the right.

  * •

$r_{3}$’s supporting line has the equation $y=0$, its starting point is
$o_{3}=(2,0)$ and the ray is pointing towards the right.

Let $T_{p}$ be a pseudo-tour going from $s$ to point $p_{1}=(0,1)$ and back to
$s$. $T_{p}$ is a feasible pseudo-tour starting and ending at $s$, since it
reflects on $r_{2}$ and makes crossing contact with the supporting lines of
$r_{1}$ and $r_{3}$. Furthermore, let $T$ be a tour starting at $s$, visiting
$r_{1}$ at $o_{1}$, $r_{2}$ at point $(\frac{1}{2},1)$ and $r_{3}$ at $o_{3}$
before returning to point $s$. This is a feasible tour starting and ending at
$s$ since it visits all three rays of the input instance.

See Figure 10 for an illustration of the input instance as well as $T_{p}$ and
$T$.

We claim that $T_{p}$ and $T$ are an optimal pseudo-tour and tour respectively
for the input instance. The lemma would then directly follow for $r=r_{1}$,
since $r_{1}$ is not visited by $T_{p}$, its origin $o_{1}$ is on
$\mathcal{H}$ which is defined by the vertices $o_{1},p_{1},o_{3}$ and $s$,
and $T$ does not make a crossing contact with $r_{1}$ at $o_{1}$ (it does what
Tan [17] calls a bending contact). Since the optimal tour and pseudo tour are
unique the lemma then follows.

Figure 10: A counterexample to the statement of Lemma $6$ from [17]

Regarding the optimality of $T_{p}$, note that any feasible pseudo-tour must
either reflect on $r_{2}$ or make a crossing contact with the supporting line
of $r_{2}$. Since the distance between $s$ and the supporting line of $r_{2}$
is $1+\epsilon$, any feasible pseudo-tour for the instance must therefore have
a total length of at least $2+2\epsilon$. Since $T_{p}$ has a total length of
$2+2\epsilon$ it must be optimal.

Regarding the optimality of $T$, we first observe that by the triangle
inequality the optimal tour must consist of $4$ line segments with endpoints
at $s$, $r_{1}$, $r_{2}$ and $r_{3}$. We first show that $T$ is shortest among
all tours that start from $s$, visit $r_{1}$ followed by $r_{2}$ and then
$r_{3}$ before returning to $s$. We will then show that any tour visiting the
rays in a different order must have a strictly higher cost.

By construction, the shortest possible line segment connecting $s$ and $r_{1}$
is $so_{1}$ and similarly the shortest possible line segment connecting $s$
and $r_{3}$ is $so_{3}$. Furthermore, the shortest possible path from $r_{1}$
to $r_{3}$ through $r_{2}$ is the one from $o_{1}$ to $p_{3}$ to $o_{3}$.
Therefore $T$ is the shortest possible tour that goes from $s$ to $r_{1}$ to
$r_{2}$ and then $r_{3}$ before returning to $s$. Note that the length of $T$
is exactly $\sqrt{1+\epsilon^{2}}+2\sqrt{1.5^{2}+1}+\sqrt{4+\epsilon^{2}}$
which is strictly less than $6.8$ for any $\epsilon<0.1$.

The only two other distinct possible orders of visitation are
$s,r_{2},r_{1},r_{3}$ and then going back to $s$, and $s,r_{1},r_{3}$ and
$r_{2}$ before returning to $s$. The first one has a total length of at least
$(1+\epsilon)+1+3+\sqrt{4+\epsilon^{2}}$ by taking the respective minimum
distances between the objects. This total length is strictly greater than $7$.
In a similar way, the second one has a total length of at least
$\sqrt{1+\epsilon^{2}}+3+2\sqrt{2}$ which is strictly greater than $6.8$. This
concludes the proof.