Indian Institute of Technology Kharagpur,
<EMAIL_ADDRESS>Institute of Technology Kharagpur,
<EMAIL_ADDRESS>Indian Institute of Technology Kharagpur,
<EMAIL_ADDRESS>Theory of computation Computational geometry Petr
A. Golovach and Meirav Zehavi 2 16th International Symposium on Parameterized
and Exact Computation (IPEC 2021) IPEC 2021 IPEC 2021 September 8–10, 2021
Lisbon, Portugal 214 2

# Efficient Algorithms for on Near-Convex Terminal Sets

Anubhav Dhar  Soumita Hait  Sudeshna Kolay

###### Abstract

The problem takes as input a set $\mathcal{P}$ of points in the Euclidean
plane and finds the minimum length network interconnecting all the points of
$\mathcal{P}$. In this paper, in continuation to the works of [5] and [16], we
study when $\mathcal{P}$ is formed by the vertices of a pair of regular,
concentric and parallel $n$-gons. We restrict our attention to the cases where
the two polygons are not very close to each other. In such cases, we show that
is polynomial-time solvable, and we describe an explicit structure of a
Euclidean Steiner minimal tree for $\mathcal{P}$.

We also consider point sets $\mathcal{P}$ of size $n$ where the number of
input points not on the convex hull of $\mathcal{P}$ is $f(n)\leq n$. We give
an exact algorithm with running time $2^{\mathcal{O}(f(n)\log n)}$ for such
input point sets $\mathcal{P}$. Note that when $f(n)=\mathcal{O}(\frac{n}{\log
n})$, our algorithm runs in single-exponential time, and when $f(n)=o(n)$ the
running time is $2^{o(n\log n)}$ which is better than the known algorithm in
[9].

We know that no FPTAS exists for unless $\mbox{P}=\mbox{NP}$ [6]. On the other
hand FPTASes exist for on convex point sets [14]. In this paper, we show that
if the number of input points in $\mathcal{P}$ not belonging to the convex
hull of $\mathcal{P}$ is $\mathcal{O}(\log n)$, then an FPTAS exists for . In
contrast, we show that for any $\epsilon\in(0,1]$, when there are
$\Omega(n^{\epsilon})$ points not belonging to the convex hull of the input
set, then no FPTAS can exist for unless $\mbox{P}=\mbox{NP}$.

###### keywords:

Steiner minimal tree, Euclidean Geometry, Almost Convex point sets, FPTAS,
strong NP-completeness

###### category:

##  1 Introduction

The problem asks for a network of minimum total length interconnecting a given
finite set $\mathcal{P}$ of $n$ points in the Euclidean plane. Formally, we
define the problem as follows, taken from [2]:

Input: A set $\mathcal{P}$ of $n$ points in the Euclidean plane Question: Find
a connected plane graph $\mathcal{T}$ such that $\mathcal{P}$ is a subset of
the vertex set $V(\mathcal{T})$, and for the edge set $E(\mathcal{T})$,
$\Sigma_{e\in E(\mathcal{T})}\overline{e}$ is minimized over all connected
plane graphs with $\mathcal{P}$ as a vertex subset.

Note that the metric being considered is the Euclidean metric, and for any
edge $e\in E(\mathcal{T})$, $\overline{e}$ denotes the Euclidean length of the
edge. Here, the input set $\mathcal{P}$ of points is often called a set of
terminals, the points in $\mathcal{S}=V(\mathcal{T})\setminus\mathcal{P}$ are
called Steiner points. A solution graph $\mathcal{T}$ is referred to as a
Euclidean Steiner minimal tree, or simply an SMT.

The problem is a classic problem in the field of Computational Geometry. The
origin of the problem dates back to Fermat (1601-1665) who proposed the
problem of finding a point in the plane such that the sum of its distance from
three given points is minimized. This is equivalent to finding the location of
the Steiner point when given three terminals as input. Torricelli proposed a
geometric solution to this special case of 3 terminal points. The idea was to
construct equilateral triangles outside on all three sides of the triangle
formed by the terminals, and draw their circumcircles. The three circles meet
at a single point, which is our required Steiner point. This point came to be
known as the Torricelli point. When one of the angles in the triangle is at
least $120^{\circ}$, the minimizing point coincides with the obtuse angle
vertex of the triangle. In this case, the Torricelli point lies outside the
triangle and no longer minimizes the sum of distances from the vertices.
However, when vertices of polygons with more than 3 sides are considered as a
set of terminals, a solution to the Fermat problem does not in general lead to
a solution to the problem. For a more detailed survey on the history of the
problem, please refer to [2, 9]. For convenience, we refer to the problem as
ESMT.

ESMT is NP-hard. In [6], Garey et al. prove a discrete version of the problem
(Discrete ESMT) to be strongly NP-complete via a reduction from the Exact
Cover by 3-Sets (X3C) problem. Although it is not known if the ESMT problem is
in NP, it is at least as hard as any NP-complete problem. So, we do not expect
a polynomial time algorithm for it. A recursive method using only Euclidean
constructions was given by Melzak in [11] for constructing all the Steiner
minimal trees for any set of $n$ points in the plane by constructing full
Steiner trees of subsets of the points. Full Steiner trees are interconnecting
trees having the maximum number of newly introduced points (Steiner points)
where all internal junctions are of degree $3$. Hwang improved the running
time of Melzak’s original exponential algorithm for full Steiner tree
construction to linear time in [8]. Using this, we can construct an Euclidean
Steiner minimal tree in $2^{\mathcal{O}(n\log n)}$ time for any set of $n$
points. This was the first algorithm for . The problem is known to be NP-hard
even if all the terminals lie on two parallel straight lines, or on a bent
line segment where the bend has an angle of less than $120^{\circ}$ [13].
Since the above sets of terminals all lie on the boundary of a convex polygon
(or, are in convex position), this shows that ESMT is NP-hard when restricted
to a set of points that are in weakly convex position.

Although the ESMT problem is NP-hard, there are certain arrangements of points
in the plane for which the Euclidean Steiner minimal tree can be computed
efficiently, say in polynomial time. One such arrangement is placing the
points on the vertices of a regular polygon. This case was solved by Du et al.
[5]. Their work gives exact topologies of the Euclidean Steiner minimal trees.
Weng et al. [16] generalized the problem by incorporating the centre point of
the regular polygon as part of the terminal set, along with the vertices. This
case was also found to be polynomial time solvable.

Tractability in the form of approximation algorithms for ESMT has been
extensively studied. It was proved in [6] that a fully polynomial time
approximation scheme (FPTAS) cannot exist for this problem unless
$\mbox{P}=\mbox{NP}$. However, we do have an FPTAS when the terminals are in
convex position [14]. Arora’s celebrated polynomial time approximation scheme
(PTAS) for the ESMT and other related problems is described in [1]. Around the
same time, Rao and Smith gave an efficient polynomial time approximation
scheme (EPTAS) in [12]. In recent years, an EPTAS with an improved running
time was designed by Kisfaludi-Bak et al. [10].

#### Our Results.

In this paper, we first extend the work of [5] and [16]. We state this problem
as ESMT on $k$-Concentric Parallel Regular $n$-gons.

######  Definition 1.1 ($k$-Concentric Parallel Regular $n$-gons).

$k$-Concentric Parallel Regular $n$-gons are $k$ regular $n$-gons that are
concentric and where the corresponding sides of polygons are parallel to each
other.

Please refer to Figure 1(a) for an example of a $2$-Concentric Parallel
Regular $12$-gon. We call $k$-Concentric Parallel Regular $n$-gons as $k$-CPR
$n$-gons for short.

We consider terminal sets where the terminals are placed on the vertices of
$2$-CPR $n$-gons. In the case of $k=2$, the $n$-gon with the smaller side
length will be called the inner $n$-gon and the other $n$-gon will be called
the outer $n$-gon. Also, let $a$ be the side length of the inner $n$-gon, and
$b$ be the side length of the outer $n$-gon. We define $\lambda=\frac{b}{a}$
and refer to it as the _aspect ratio_ of the two regular polygons. In Section
3, we derive the exact structures of the SMTs for $2$-CPR $n$-gons when the
aspect ratio $\lambda$ of the two polygons is greater than
$\frac{1}{1-4\sin{(\pi/n)}}$ and $n\geq 13$.

Next, we consider ESMT on an $f(n)$-Almost Convex Point Set.

######  Definition 1.2 ($f(n)$-Almost Convex Point Set).

An $f(n)$-Almost Convex Point Set $\mathcal{P}$ is a set of $n$ points in the
Euclidean plane such that there is a partition
$\mathcal{P}=\mathcal{P}_{1}\uplus\mathcal{P}_{2}$ where $\mathcal{P}_{1}$
forms the convex hull of $\mathcal{P}$ and $|\mathcal{P}_{2}|=f(n)$.

Please refer to Figure 1(b) for an example of a $5$-Almost Convex Set of $13$
points. In Section 4, we give an exact algorithm for ESMT on $f(n)$-Almost
Convex Sets of $n$ terminals. The running time of this algorithm is
$2^{\mathcal{O}(f(n)\log n)}$. Thus, when $f(n)=\mathcal{O}(\frac{n}{\log
n})$, then our algorithm runs in $2^{\mathcal{O}(n)}$ time, and when
$f(n)=o(n)$ then the running time is $2^{o(n\log n)}$. This is an improvement
on the best known algorithm for the general case [9].

Next, for $f(n)=\mathcal{O}(\log n)$, we give an FPTAS in Section 5.1. On the
other hand in Section 5.2 we show that, for all $\epsilon\in(0,1]$, when
$f(n)\in\Omega(n^{\epsilon})$, there cannot exist any FPTAS unless
$\mbox{P}=\mbox{NP}$.

(a)

(b)

Figure 1: Examples for Definition 1.1 and Definition 1.2

##  2 Preliminaries

##### Notations.

For a given positive integer $k\in\mathbb{N}$, the set of integers
$\\{1,2,\ldots,k\\}$ is denoted for short as $[k]$. Given a graph $G$, the
vertex set is denoted as $V(G)$ and the edge set as $E(G)$. Given two graphs
$G_{1}$ and $G_{2}$, $G_{1}\cup G_{2}$ denotes the graph $G$ where
$V(G)=V(G_{1})\cup V(G_{2})$ and $E(G)=E(G_{1})\cup E(G_{2})$.

In this paper, a regular $n$-gon is denoted by $A_{1}A_{2}A_{3}...A_{n}$ or
$B_{1}B_{2}B_{3}...B_{n}$. For convenience, we define $A_{n+1}:=A_{1}$,
$B_{n+1}:=B_{1}$, $A_{0}:=A_{n}$ and $B_{0}:=B_{n}$. We use the notation
$\\{A_{i}\\}$ to denote the polygon $A_{1}A_{2}A_{3}\ldots A_{n}$ and
$\\{B_{i}\\}$ to denote the polygon $B_{1}B_{2}B_{3}\ldots B_{n}$. For any
regular polygon $A_{1}A_{2}A_{3}...A_{n}$, the circumcircle of the polygon is
denoted as $(A_{1}A_{2}A_{3}...A_{n})$. Given any $n$-vertex polygon in the
Euclidean plane with vertices $\mathcal{P}=P_{1}P_{2}P_{3}\ldots P_{n}$, and
interval in $\mathcal{K}$ is a subset of consecutive vertices
$P_{i}P_{i+1\ldots P_{j}}$, $i,j\in[n]$, also denoted as $[P_{i},P_{j}]$. Here
$P_{i}$ is considered the starting vertex of the interval and $P_{j}$ the
ending vertex. For any $P_{k}$, $i\leq k\leq j$ in the interval we will also
use the notation $P_{i}\leq P_{k}\leq P_{j}$.

Given two points $P$, $Q$ in the Euclidean plane, we denote by ${\sf
dist}(P,Q)$ the Euclidean distance between $P$ and $Q$. Given a line segment
$AB$ in the Euclidean plane, $\overline{AB}={\sf dist}(A,B)$. For two distinct
points $A$ and $B$, $L_{AB}$ denotes the line containing $A$ and $B$; and
$\overrightarrow{AB}$ denotes the ray originating from $A$ and containing $B$.

When we refer to a graph $\mathcal{G}$ in the Euclidean plane then
$V(\mathcal{G})$ is a set of points in the Euclidean plane, and
$E(\mathcal{G})$ is a subset of the family of line segments
$\\{P_{1}P_{2}|P_{1},P_{2}\in V(\mathcal{G})\\}$. For any tree $\mathcal{T}$
in the Euclidean plane, we denote by the notation $|\mathcal{T}|$ the value of
$\Sigma_{e\in E(\mathcal{T})}\overline{e}$. A path in a tree $\mathcal{T}$ is
uniquely specified by the sequence of vertices on the path; therefore,
$P_{1}$, $P_{2}$, $P_{3}$, …, $P_{k}$ (where $P_{i}\in V(\mathcal{T}),\forall
i\in[k]$ and $P_{i}P_{i+1}\in E(\mathcal{T}),\forall i\in[k-1]$) denotes the
path starting from the vertex $P_{1}$, going through the vertices $P_{2}$,
$P_{3}$, …, $P_{k-1}$ and finally ending at $P_{k}$. Equivalently, we can
specify the same path as _the path from $P_{1}$ to $P_{k}$_, since
$\mathcal{T}$ is a tree. Consider the graph $T$ such that $V(T)=\\{v_{P}|P\in
V(\mathcal{T})\\}$, $E(T)=\\{v_{P_{1}}v_{P_{2}}|P_{1}P_{2}\mbox{ is a line
segment in }E(\mathcal{T})\\}$. Then $T$ is said to be the topology of
$\mathcal{T}$ while $\mathcal{T}$ is said to realize the topology $T$. Given
two trees $\mathcal{T}_{1}$, $\mathcal{T}_{2}$ in the Euclidean plane,
$\mathcal{T}^{\prime}=\mathcal{T}_{1}\cup\mathcal{T}_{2}$ is the graph where
$V(\mathcal{T}^{\prime})=V(\mathcal{T}_{1})\cup V(\mathcal{T}_{2})$ and
$E(\mathcal{T}^{\prime})=E(\mathcal{T}_{1})\cup E(\mathcal{T}_{2})$.

Given any graph $G$, a Steiner minimal tree or SMT for a terminal set
$\mathcal{P}\subseteq V(G)$ is the minimum length connected subgraph
$G^{\prime}$ of $G$ such that $\mathcal{P}\subseteq V(G^{\prime})$. The
Steiner Minimal Tree problem on graphs takes as input a set $\mathcal{P}$ of
terminals and aims to find a minimum length SMT for $\mathcal{P}$. For the
rest of the paper, we also refer to a Euclidean Steiner minimal tree as an
SMT. Given a set of points $\mathcal{P}$ in the Euclidean plane, the convex
hull of $\mathcal{P}$ is denoted as $\mathrm{CH(\mathcal{P})}$.

##### Euclidean Minimum Spanning Tree (MST).

Given a set $\mathcal{P}$ of $n$ points in the Euclidean plane, let $G$ be a
graph where $V(G)=\\{v_{P}|P\in\mathcal{P}\\}$ and
$E(G)=\\{v_{P_{i}}v_{P_{j}}|P_{i},P_{j}\in\mathcal{P}\\}$. Also, a weight
function $w_{G}:E(T)\rightarrow\mathbb{R}$ is defined such that for each edge
$v_{P_{1}}v_{P_{2}}\in E(T)$,
$w_{G}(v_{P_{1}}v_{P_{2}})=\overline{P_{1}P_{2}}$. The Euclidean minimum
spanning tree of a set $\mathcal{P}$ is the minimum spanning tree of the graph
$G$ with edge weights $w_{G}$. Note that a Steiner tree may have shorter
length than a minimum spanning tree of the point set $\mathcal{P}$.

In the plane, the Euclidean minimum spanning tree is a subgraph of the
Delaunay triangulation. Using this fact, the Euclidean minimum spanning tree
for a given set of points in the Euclidean plane can be found in
$\mathcal{O}(n\log n)$ time as discussed in [15].

##### Properties of a Euclidean Steiner minimal tree.

A Euclidean Steiner minimal tree (SMT) has certain structural properties as
given in [3]. We state them in the following Proposition.

######  Proposition 2.1.

Consider an SMT on $n$ terminals.

  1. 1.

No two edges of the SMT intersect with each other.

  2. 2.

Each Steiner point has degree exactly $3$ and the incident edges meet at
$120^{\circ}$ angles. The terminals have degree at most $3$ and the incident
edges form angles that are at least $120^{\circ}$.

  3. 3.

The number of Steiner points is at most $n-2$, where $n$ is the number of
terminals.

A full Steiner tree (FST) is a Steiner tree (need not be minimal, but may
include Steiner points) having exactly $n-2$ Steiner points, where $n$ is the
number of terminals. In an FST, all terminals are leaves and Steiner points
are interior nodes. When the length of an FST is minimized, it is called a
minimum FST.

All SMTs can be decomposed into FST components such that, in each component a
terminal is always a leaf. This decomposition is unique for a given SMT [9]. A
topology for an FST is called a full Steiner topology and that of a Steiner
tree is called a Steiner topology.

##### Steiner Hulls.

A Steiner hull for a given set of points is defined to be a region which is
known to contain an SMT. We get the following propositions from [9].

######  Proposition 2.2.

For a given set of terminals, every SMT is always contained inside the convex
hull of those points. Thus, the convex hull is also a Steiner hull.

The next two propositions are useful in restricting the structure of SMTs and
the location of Steiner points.

######  Proposition 2.3 (The Lune property).

Let $\rm UV$ be any edge of an SMT. Let $L(\rm{U},\rm{V})$ be the lune-shaped
intersection of circles of radius $|\rm UV|$ centered on $\rm U$ and $\rm V$.
No other vertex of the SMT can lie in $L(\rm{U},\rm{V})$, except $U$ and $V$
themselves.

######  Proposition 2.4 (The Wedge property).

Let $W$ be any open wedge-shaped region having angle $120^{\circ}$ or more and
containing none of the points from the input terminal set $\mathcal{P}$. Then
$W$ contains no Steiner points from an SMT of $\mathcal{P}$.

##### Approximation Algorithms.

We define all the necessary terminology required in terms of a minimization
problem, as ESMT is a minimization problem.

######  Definition 2.5 (Efficient Polynomial Time Approximation Scheme
(EPTAS)).

An algorithm is called an efficient polynomial time approximation scheme
(EPTAS) for a problem if it takes an input instance and a parameter
$\epsilon>0$, and outputs a solution with approximation factor $(1+\epsilon)$
for a minimization problem in time $f(1/\epsilon)n^{\mathcal{O}(1)}$ where $n$
is the input size and $f(1/\epsilon)$ is any computable function.

######  Definition 2.6 (Fully Polynomial Time Approximation Scheme (FPTAS)).

An algorithm is called a fully polynomial time approximation scheme (FPTAS)
for a problem if it takes an input instance and a parameter $\epsilon>0$, and
outputs a solution with approximation factor $(1+\epsilon)$ for a minimization
problem in time $(1/\epsilon)^{\mathcal{O}(1)}n^{\mathcal{O}(1)}$ where $n$ is
the input size.

##  3 Polynomial cases for

In this section, we consider the problem for $2$-CPR $n$-gons. Throughout the
section, we denote the inner $n$-gon as $\\{A_{i}\\}$ and the outer $n$-gon as
$\\{B_{i}\\}$. First, we consider the configuration of an Euclidean Steiner
minimal tree in a subsection of the annular area between $\\{A_{i}\\}$ and
$\\{B_{i}\\}$, which will form an isosceles trapezoid. Next, we consider the
simple but illustrative case of $n=3$. Finally we prove our result for all
$n$.

###  3.1 Isosceles Trapezoids and Vertical Forks

In this section, we discuss one particular Steiner topology when the terminal
set is formed by the four corners of a given isosceles trapezoid. However, we
will limit the discussion to only the isosceles trapezoids such that the angle
between the non-parallel sides is of the form $\frac{2\pi}{n}$ where
$n\in\mathbb{N}$, $n\geq 4$. The reason is that given $2$-CPR $n$-gons
$\\{A_{i}\\}$, $\\{B_{i}\\}$, for $n\geq 4$ and for any
$j\in\\{1,\ldots,n-1\\}$, the region $A_{j}A_{j+1}B_{j}B_{j+1}$ is an
isosceles trapezoid such that the angle between the non-parallel sides is of
the form $\frac{2\pi}{n}$.

Figure 2: Isosceles trapezoid with $\angle AOB=\frac{2\pi}{8}$

Let $ABQP$ be an isosceles trapezoid with $AB$, $PQ$ as the parallel sides,
and $AP$, $BQ$ as the non-parallel sides. Assume without loss of generality
that $AB$ is shorter in length than $PQ$. Let $\overline{AB}=1$ and
$\overline{PQ}=\lambda$, where
$\lambda\geq\frac{\sqrt{3}+\tan{\frac{\pi}{n}}}{\sqrt{3}-\tan{\frac{\pi}{n}}}$.
For brevity, we say
$\lambda_{v}=\frac{\sqrt{3}+\tan{\frac{\pi}{n}}}{\sqrt{3}-\tan{\frac{\pi}{n}}}$.
Let $L_{PA}$ and $L_{QB}$ be the lines containing the line segments $PA$ and
$QB$ respectively. Also let $O$ be the point of intersection of $L_{PA}$ and
$L_{QB}$. Further, let $M$ and $N$ be the midpoints of $AB$ and $PQ$
respectively (as in Figure 2). As mentioned earlier, $\angle
AOB=\frac{2\pi}{n}$ where $n\in\mathbb{N}$, $n\geq 4$.

Now, we explore the following Steiner topology of the terminal set
$\\{A,B,P,Q\\}$:

  1. 1.

$A$ and $B$ are connected to a Steiner point $S_{1}$.

  2. 2.

$P$ and $Q$ are connected to another Steiner point $S_{2}$.

  3. 3.

$S_{1}$ and $S_{2}$ are directly connected (Please see Figure 3).

We call such a topology a _vertical fork topology_ and the Steiner tree
realising such a topology, the _vertical fork_. Note that in a vertical fork
topology the only unknowns are the locations of the two Steiner points
$S_{1},S_{2}$. Therefore, we have the vertical fork topology as $T_{vf}$, with
$E(T_{vf})=\\{AS_{1},BS_{1},S_{1}S_{2},S_{2}P,S_{2}Q\\}$.

Figure 3: The Vertical Fork, $\mathcal{T}_{vf}$

We show the existence of a vertical fork and calculate its total length in the
following lemma.

######  Lemma 3.1.

A vertical fork $\mathcal{T}_{vf}$ can be constructed for any $n\geq 4$ and
for any $\lambda\geq\lambda_{v}$, where

$\lambda_{v}=\frac{\sqrt{3}+\tan{\frac{\pi}{n}}}{\sqrt{3}-\tan{\frac{\pi}{n}}}$

such that the length of the vertical fork

$|\mathcal{T}_{vf}|=\dfrac{(\lambda-1)}{2\tan\frac{\pi}{n}}+\dfrac{\sqrt{3}(\lambda+1)}{2}$

######  Proof 3.2.

First, we construct the Steiner points $S_{1}$, $S_{2}$ and then prove that
the construction works.

In the following construction, we describe how to find the locations of
$S_{1}$ and $S_{2}$ for the vertical fork:

  * •

We construct equilateral triangles $ABE$ and $PQF$ where both points $E$ and
$F$ lie outside the trapezoid $ABQP$.

  * •

We construct the circumcircles $(ABE)$ and $(PQF)$ of $ABE$ and $PQF$,
respectively.

  * •

Recall that $L_{MN}$ is the line segment containing $M$ and $N$. Define
$S_{1}$ to be the point of intersection of $L_{MN}$ and the circle $(ABE)$
distinct from $E$; similarly, $S_{2}$ is the point of intersection of the
$L_{MN}$ and $(PQF)$ distinct from $F$. Therefore, by construction, $S_{2}$,
$M$ must lie on the same side of $N$ on $L_{MN}$, and $S_{1}$, $N$ must lie on
the same side of $M$ on $L_{MN}$. Further, $\angle AS_{1}B=\angle
PS_{2}Q=\frac{2\pi}{3}$ by construction.

We now show that the points $S_{1}$ and $S_{2}$ indeed lie inside the line
segment $MN$ and the points appear in the order: $M$, $S_{1}$, $S_{2}$, $N$.
We prove the following claim to serve this purpose.

######  Claim 1.

$\overline{S_{1}M}+\overline{S_{2}N}\leq\overline{MN}$

######  Proof 3.3.

We have
$\overline{MN}=\overline{ON}-\overline{OM}=\dfrac{\lambda}{2\tan\frac{\pi}{n}}-\dfrac{1}{2\tan\frac{\pi}{n}}=\dfrac{(\lambda-1)}{2\tan\frac{\pi}{n}}$
Again $\overline{S_{1}M}=\dfrac{1}{2\sqrt{3}}$ and
$\overline{S_{2}N}=\dfrac{\lambda}{2\sqrt{3}}$.
Therefore we have

$\displaystyle\overline{MN}-(\overline{S_{1}M}+\overline{S_{2}M})$
$\displaystyle=$
$\displaystyle\dfrac{(\lambda-1)}{2\tan\frac{\pi}{n}}-\dfrac{1}{\sqrt{3}}-\dfrac{\lambda}{2\sqrt{3}}$
$\displaystyle=$
$\displaystyle\dfrac{(\lambda-1)}{2\tan\frac{\pi}{n}}-\dfrac{(\lambda+1)}{2\sqrt{3}}$
$\displaystyle=$
$\displaystyle\frac{\lambda(\sqrt{3}-\tan\frac{\pi}{n})-(\sqrt{3}+\tan\frac{\pi}{n})}{2\sqrt{3}\tan\frac{\pi}{n}}$
$\displaystyle=$
$\displaystyle\frac{\sqrt{3}-\tan\frac{\pi}{n}}{2\sqrt{3}\tan\frac{\pi}{n}}\cdot(\lambda-\lambda_{v})$

Therefore $\lambda\geq\lambda_{v}$ implies
$\overline{MN}\geq(\overline{S_{1}M}+\overline{S_{2}M})$. This proves 1.

From 1, we get $\overline{S_{1}M},\overline{S_{2}N}\leq\overline{MN}$. As
$S_{2}$, $M$ lie on the same side of $N$ on $L_{MN}$ and $S_{1}$, $N$ lie on
the same side of $M$ on $L_{MN}$, this implies that $S_{1}$, $S_{2}$ lie on
the line segment $MN$. Further,
$\overline{S_{1}M}+\overline{S_{2}N}\leq\overline{MN}$ implies
$\overline{S_{1}M}\leq\overline{S_{2}M}\leq\overline{NM}$, which in turn
implies that the points appear in the order: $M$, $S_{1}$, $S_{2}$. $N$.

Now, we calculate the total length of the vertical fork, $|\mathcal{T}_{v}f|$:

$\displaystyle|\mathcal{T}_{vf}|$ $\displaystyle=$
$\displaystyle\overline{AS_{1}}+\overline{BS_{1}}+\overline{S_{1}S_{2}}+\overline{PS_{2}}+\overline{QS_{2}}$
$\displaystyle=$ $\displaystyle
2\overline{PS_{2}}+2\overline{AS_{1}}+\overline{S_{1}S_{2}}$ $\displaystyle=$
$\displaystyle\dfrac{2\lambda}{\sqrt{3}}+\dfrac{2}{\sqrt{3}}+\bigg{(}\dfrac{(\lambda-1)}{2\tan\frac{\pi}{n}}-\dfrac{(\lambda+1)}{2\sqrt{3}}\bigg{)}$
$\displaystyle=$
$\displaystyle\dfrac{(\lambda-1)}{2\tan\frac{\pi}{n}}+\dfrac{\sqrt{3}(\lambda+1)}{2}$

This completes the proof of Lemma 3.1.

###  3.2 for $2$-Concentric Parallel Regular $3$-gons

Note that a regular $3$-gon is an equilateral triangle and therefore, for the
rest of this section we call a regular $3$-gon as an equilateral triangle. We
describe a minimal solution for for $2$-CPR equilateral triangles.

######  Lemma 3.4.

Consider two concentric and parallel equilateral triangles $A_{1}A_{2}A_{3}$
and $B_{1}B_{2}B_{3}$, where $B_{1}B_{2}B_{3}$ has side length $\lambda>1$ and
$A_{1}A_{2}A_{3}$ has side length $1$. An SMT of
$\\{A_{1},A_{2},A_{3},B_{1},B_{2},B_{3}\\}$ is an SMT of
$\\{B_{1},B_{2},B_{3}\\}$, and has length $\sqrt{3}\cdot\lambda$.

######  Proof 3.5.

It is to be noted that the centre $O$ of both $A_{1}A_{2}A_{3}$ and
$B_{1}B_{2}B_{3}$ is also the Torricelli point of both $A_{1}A_{2}A_{3}$ and
$B_{1}B_{2}B_{3}$ [5]. On taking $O$ as the only Steiner point, the SMT for
$\\{B_{1},B_{2},B_{3}\\}$ is $\mathcal{T}_{3}=\\{OB_{1},OB_{2},OB_{3}\\}$ [5].
However, the edges of $\mathcal{T}_{3}$ already pass through $A_{1}$, $A_{2}$
and $A_{3}$. Therefore, $\mathcal{T}_{3}$ with
$E(\mathcal{T}_{3})=\\{OA_{1},OA_{2},OA_{3},A_{1}B_{1},A_{2}B_{2},A_{3}B_{3}\\}$
is also the SMT for $\\{A_{1},A_{2},A_{3},B_{1},B_{2},B_{3}\\}$ as shown in
Figure 4.

From the definition of $\mathcal{T}_{3}$, we have the length of the SMT for
$\\{A_{i}\\}\cup\\{B_{i}\\}$ , for $n=3$ as

$|\mathcal{T}_{3}|=\sqrt{3}\cdot\lambda$

Figure 4: SMT for $2$-CPR $3$-gons

###  3.3 and Large Polygons with Large Aspect Ratios

In this section, we consider the problem when the terminal set is formed by
the vertices of $2$-CPR $n$-gons, namely $\\{A_{i}\\}$ and $\\{B_{i}\\}$. As
mentioned earlier, $\\{A_{i}\\}$ is the inner polygon and $\\{B_{i}\\}$ is the
outer polygon of this set of $2$-CPR $n$-gons. In particular, we consider the
case when $n\geq 13$; for $n\leq 12$ these are constant sized input instances
and can be solved using any brute-force technique. We also require that the
aspect ratio $\lambda$ has a lower bound $\lambda_{1}$, i.e. we do not want
the two polygons to have sides of very similar length. The exact value of
$\lambda_{1}$ will be clear during the description of the algorithm.
Intuitively, when $\lambda$ is _very large_ , the SMT should look similar to
what was derived in [16]. In other words, (please refer to Figure 5):

  1. 1.

for some $j\in[n]$, there is a vertical fork connecting the two consecutive
inner polygon points $A_{j},A_{j+1}$ with the two consecutive outer polygon
points $B_{j},B_{j+1}$ \- we refer to this vertical fork as the _vertical
gadget_ for the SMT,

  2. 2.

the other points in $\\{B_{i}\\}$ are connected directly via $(n-2)$ outer
polygon edges,

  3. 3.

the other points in $\\{A_{i}\\}$ are connected via $(n-2)$ inner polygon
edges.

We call such a topology, a _singly connected topology_ as in Figure 5. For the
rest of this section, we consider the SMTs for a large enough aspect ratio,
$\lambda$ and show that there is an SMT that must be a realisation of a
_singly connected topology_. We refer to an SMT for the terminal set defined
by the vertices of $\\{A_{i}\\}$ and $\\{B_{i}\\}$ as the SMT for
$\\{A_{i}\\}\cup\\{B_{i}\\}$ .

Without loss of generality, we consider the edge length of any side
$A_{i}A_{i+1}$ in $\\{A_{i}\\}$ to be $1$. As we defined the aspect ratio to
be $\lambda$, any side $B_{i}B_{i+1}$ of $\\{B_{i}\\}$ must have a side length
of $\lambda$. Further, we observe that for any SMT $\mathcal{T}$, specifying
$E(\mathcal{T})$ sufficiently determines the entire tree, as
$V(\mathcal{T})=\\{P\leavevmode\nobreak\ |\leavevmode\nobreak\ \exists Q\text{
such that }PQ\in E(\mathcal{T})\\}$.

We start with the following formal definitions:

######  Definition 3.6.

A Steiner topology of $\\{A_{i}\\}\cup\\{B_{i}\\}$ is a singly connected
topology, if it has the following structure:

  * •

A vertical gadget i.e. five edges
$\\{A_{j}S_{a},A_{j+1}S_{a},S_{a}S_{b},S_{b}B_{j},S_{b}B_{j+1}\\}$ for some
$1\leq j\leq n$, where $S_{a}$ and $S_{b}$ are newly introduced Steiner points
contained in the isosceles trapezoid $\\{A_{j},A_{j+1},B_{j},B_{j+1}\\}$.

  * •

All $(n-2)$ polygon edges of $\\{A_{i}\\}$ excluding the edge $A_{j}A_{j+1}$

  * •

All $(n-2)$ polygon edges of $\\{B_{i}\\}$ excluding the edge $B_{j}B_{j+1}$

(a)

(b)

Figure 5:  _Singly connected topology_ of $2$-CPR $n$-gons $n=13$ and $n=20$

We define the notion of a path in an SMT for the vertices of $\\{A_{i}\\}$ and
$\\{B_{i}\\}$ where the starting point is in $\\{A_{i}\\}$ and the ending
point is in $\\{B_{i}\\}$.

######  Definition 3.7.

An A-B path is a path in a Steiner tree of $\\{A_{i}\\}\cup\\{B_{i}\\}$ which
starts from a vertex in $\\{A_{i}\\}$ and ends at a vertex in $\\{B_{i}\\}$
with all intermediate nodes (if any) being Steiner points.

The following Definition and Figure 6 is useful for the design of our
algorithm.

######  Definition 3.8.

A counter-clockwise path is a path $P_{1},P_{2},...P_{m}$ in a Steiner tree
such that for all $i\in\\{2,\ldots,m-1\\},\angle
P_{i-1}P_{i}P_{i+1}=\frac{2\pi}{3}$ in the counter-clockwise direction.
Similarly, a clockwise path is a path $P_{1},P_{2},...P_{m}$ in a Steiner tree
such that for all $i\in\\{2,\ldots,m-1\\},\angle
P_{i-1}P_{i}P_{i+1}=\frac{4\pi}{3}$ in the counter-clockwise direction.

Figure 6: $\angle P_{i-1}P_{i}P_{i+1}=\alpha$ in the counter-clockwise
direction and $\angle P_{i-1}P_{i}P_{i+1}=\beta$ in the clockwise direction,
as in Definition 3.8

Now, we consider any Steiner point $S$ in any SMT. Let $P$ and $Q$ be two
neighbours of $S$. We now prove that there is no point of the SMT inside the
triangle $PSQ$.

Let $S$ be a Steiner point in any SMT for $\\{A_{i}\\}\cup\\{B_{i}\\}$, with
neighbours $P$ and $Q$. Then, no point of the SMT lies inside the triangle
$PSQ$.

######  Proof 3.9.

By the _lune property_ (Proposition 2.3), for any edge $P_{1}Q_{1}$ in an SMT,
for the two circles centred at $P_{1}$ and at $Q_{1}$, respectively and both
having a radius of $\overline{P_{1}Q_{1}}$, the intersection region does not
contain any point of the SMT.

Figure 7: Observation 3.3: Given triangle $PSQ$, equilateral triangles $PSE$
and $QSF$ are constructed

Let $E$ and $F$ be points on the internal angle bisector of $\angle PSQ$, such
that $\angle SPE=\angle SQF=\frac{\pi}{3}$ as shown in Figure 7. Since $E$ and
$F$ are points on the angle bisector of $\angle PSQ$, $\angle PSE=\angle
QSF=\frac{\pi}{3}$. Hence, triangles $PSE$ and $QSF$ are equilateral
triangles.

Since $PS$ is an edge in the SMT, by the lune property, the intersection of
the circles centred at $P$ and $S$, both with radius $\overline{PS}$ contain
no point inside which is a part of the SMT. Since the lune contains the entire
equilateral triangle $PSE$, no point of the SMT lies inside triangle $PSE$.
Similarly, no point of the SMT lies inside the triangle $QSF$.

Further, as $\angle PSQ=\frac{2\pi}{3}$, $\angle SPQ+\angle
SQP=\frac{\pi}{3}$. This means $\angle SPQ,\angle SQP<\frac{\pi}{3}$.
Therefore, as $\angle SPE=\angle SQF=\frac{\pi}{3}$, $E$ and $F$ must lie
outside the triangle $PSQ$. This implies that the triangle $PSQ$ is covered by
the union of the triangles $PSE$ and $QSF$. As no point of the SMT lies in
triangles $PSE$ and $QSF$, triangle $PSQ$ must contain no points of the SMT as
well.

Next, we show that in an SMT for $\\{A_{i}\\}\cup\\{B_{i}\\}$ there cannot be
any Steiner point, in the interior of the polygon $\\{A_{i}\\}$, that is a
direct neighbour of some point $B_{k}$ in the polygon $\\{B_{i}\\}$.

For any SMT for $\\{A_{i}\\}\cup\\{B_{i}\\}$ , there cannot exist a Steiner
point $S$ lying in the interior of the polygon $\\{A_{i}\\}$ such that
$SB_{k}$ is an edge in an SMT for some $B_{k}\in\\{B_{i}\\}$.

######  Proof 3.10.

For the sake of contradiction, we assume that for some SMT for
$\\{A_{i}\\}\cup\\{B_{i}\\}$ there exists a Steiner point $S$ lying in the
interior of the polygon $\\{A_{i}\\}$ such that $SB_{k}$ is an edge in the SMT
for some $B_{k}\in\\{B_{i}\\}$. Let $A_{m}A_{m+1}$ be the edge such that
$SB_{k}$ intersects $A_{m}A_{m+1}$. Without loss of generality, assume that
$A_{m}$ is closer to $B_{k}$ than $A_{m+1}$. Therefore $\angle
B_{k}A_{m}S>\angle
B_{k}A_{m}A_{m+1}\geq\frac{\pi}{2}+\frac{\pi}{n}>\frac{\pi}{2}$. This means
that $B_{k}S$ is the longest edge in the triangle $B_{k}SA_{m}$. Therefore we
can remove the edge $B_{k}S$ from the SMT and replace it with either
$B_{k}A_{m}$ or $SA_{m}$ to get another tree connecting the terminal set with
a shorter total length than what we started with, which is a contradiction.

We further analyze SMTs for $\\{A_{i}\\}\cup\\{B_{i}\\}$.

Let $\mathcal{V}=\\{A_{j},A_{j+1},\ldots,A_{k}\\}$ be the interval of
consecutive vertices of $\\{A_{i}\\}$ lying between $A_{j}$ and $A_{k}$ (which
includes $A_{j+1}$) such that $A_{j}$ is distinct from $A_{k+1}$. Let $U$ be
any point on the line segment $A_{k}A_{k+1}$. Then an SMT of
$\mathcal{V}\cup\\{U\\}$ is $\mathcal{T}$, with
$E(\mathcal{T})=\\{A_{j}A_{j+1},A_{j+1}A_{j+2},\ldots,A_{k-1}A_{k}\\}\cup\\{A_{k}U\\}$.

######  Proof 3.11.

For the sake of contradiction, assume that there exists an SMT
$\mathcal{T}^{\prime}$ of $\mathcal{V}\cup\\{U\\}$ such that
$|\mathcal{T}^{\prime}|<|\mathcal{T}|$.

From [5], we know that $\mathcal{T}_{A}$, with
$E(\mathcal{T}_{A})=\\{A_{j}A_{j+1},A_{j+1}A_{j+2},\ldots,A_{j-2}A_{j-1}\\}$
(i.e. all edges of polygon $\\{A_{i}\\}$ except $A_{j-1}A_{j}$) is an SMT of
$\\{A_{i}\\}$. Since $U\in A_{k}A_{k+1}\in E(\mathcal{T}_{A})$,
$\mathcal{T}_{A}$ must also be an SMT of $\\{A_{i}\\}\cup\\{U\\}$. However,
$\mathcal{T}_{A}$ can be partitioned as
$\mathcal{T}_{A}=\mathcal{T}\uplus\mathcal{T}_{1}$, where
$E(\mathcal{T}_{1})=\\{UA_{k+1}\\}\cup\\{A_{k+1}A_{k+2},\ldots,A_{j-2}A_{j-1}\\}$.
However, as $\mathcal{T}^{\prime}$ is assumed to be of shorter total length
than $\mathcal{T}$, $\mathcal{T}^{\prime}\cup\mathcal{T}_{1}$ is a tree,
containing $\\{A_{i}\\}$ as a vertex subset, which has a shorter total length
than $\mathcal{T}_{A}$, contradicting the optimality of $\mathcal{T}_{A}$.

We proceed by showing that in any SMT for $\\{A_{i}\\}\cup\\{B_{i}\\}$ there
exists at least one A-B path which is also a counter-clockwise path.
Symmetrically, we also show that for any SMT for $\\{A_{i}\\}\cup\\{B_{i}\\}$
there exists another clockwise A-B path which consists of only clockwise
turns. We can intuitively see that this is true because, if all clockwise
paths starting at a vertex in $\\{A_{i}\\}$ also ended in a vertex in
$\\{A_{i}\\}$, there would be enough paths to form a cycle, which is not
possible in a tree.

######  Lemma 3.12.

In any SMT for $\\{A_{i}\\}\cup\\{B_{i}\\}$ , there exists an A-B path which
is also a clockwise path and there exists an A-B path which is also a counter-
clockwise path.

######  Proof 3.13.

For the sake of contradiction, assume that for some SMT for
$\\{A_{i}\\}\cup\\{B_{i}\\}$ there is no A-B path which is a counter-clockwise
path. We pick an arbitrary vertex $A_{i_{1}}\in\\{A_{i}\\}$ such that it is
connected to at least one Steiner point (say $S_{i_{1}}$). We consider the
counter-clockwise path, $\mathcal{C}_{1}$ starting from $A_{i_{1}}S_{i_{1}}$
and ending at the first terminal point in the counter-clockwise path. By
assumption, there can be no vertex of $\\{B_{i}\\}$ in $\mathcal{C}_{1}$,
hence the endpoint must be a vertex in $\\{A_{i}\\}$. Let $A_{i_{2}}$ be the
other endpoint of $\mathcal{C}_{1}$. By definition, the penultimate vertex in
this counter-clockwise path must be a Steiner point, we call it $S_{i_{2}}$.
We again consider the counter-clockwise path starting from
$A_{i_{2}}S_{i_{2}}$, and similarly, let $A_{i_{3}}$ be the first terminal
that is encountered in this path. The penultimate vertex in this counter-
clockwise path must be a Steiner point, we call it $S_{i_{3}}$. We can repeat
this procedure indefinitely to obtain $A_{i_{4}},A_{i_{5}},A_{i_{6}},\ldots$
as there are no counter-clockwise A-B paths. However, as $\\{A_{i}\\}$ has $n$
vertices, there must be a repetition of vertices among
$A_{i_{1}},A_{i_{2}},A_{i_{3}},\ldots,A_{i_{n+1}}$, implying the existence of
a cycle in the SMT, which is a contradiction.

This symmetrically implies that there must also be a clockwise A-B path.

Our next step is to bound the number of ‘connections’ that connect the inner
polygon $\\{A_{i}\\}$ and the outer polygon $\\{B_{i}\\}$ for a large aspect
ratio, $\lambda$. As $\lambda$ increases, the area of the annular region
between the two polygons increases as well. Therefore, an increase in the
number of connections would lead to a longer total length of the SMT
considered. Consequently, we will prove that after a certain positive constant
$\lambda_{1}$, for $\lambda>\lambda_{1}$ any SMT for
$\\{A_{i}\\}\cup\\{B_{i}\\}$ will have a single ‘connection’ between the two
polygons. Moreover, [16] gives us an evidence that as
$\lambda\rightarrow\infty$, there will indeed be a single connection
connecting the outer polygon and the inner polygon for $n\geq 12$. We can
formalize this notion of existence of a single ‘connection’ with the following
lemma.

######  Lemma 3.14.

For any SMT for $\\{A_{i}\\}\cup\\{B_{i}\\}$ with $n\geq 13$ and
$\lambda>\lambda_{1}$, the number of edges needed to be removed in order to
disconnect $\\{A_{i}\\}$ and $\\{B_{i}\\}$ is 1, where

$\lambda_{1}=\frac{1}{1-4\sin\frac{\pi}{n}}$

######  Proof 3.15.

For the sake of contradiction, assume that for some SMT for
$\\{A_{i}\\}\cup\\{B_{i}\\}$ , there are at least two distinct edges in that
SMT, which are needed to be removed in order to disconnect $\\{A_{i}\\}$ and
$\\{B_{i}\\}$. We start with a claim.

######  Claim 2.

A counter-clockwise A-B path in any SMT of $\\{A_{i}\\}\cup\\{B_{i}\\}$ must
have an edge of length greater than $\lambda$.

######  Proof 3.16.

We consider a generic setting, where $\mathcal{T}$ is an SMT of some set of
terminal points $\mathcal{P}$. Let $H\in V(\mathcal{T})$ be vertex of
$\mathcal{T}$. If $\mathcal{C}$ be a counter-clockwise path starting from $H$
such that no edge in the counter clockwise path has a length of more than $r$,
for some $r\in\mathbb{R}^{+}$. Due to Lemma 2.4 (1) of [16], we know that
$\mathcal{C}$ is contained entirely in the circle centred at $H$ with radius
$2r$.

In our case, any vertex in $\\{A_{i}\\}$ and any vertex in $\\{B_{i}\\}$ are
separated by the distance of at least
$\dfrac{\lambda-1}{2\sin{\frac{\pi}{n}}}$. Therefore, by the above fact, the
maximum edge length in a counter-clockwise A-B path of any SMT of
$\\{A_{i}\\}\cup\\{B_{i}\\}$ must be at least
$\dfrac{\lambda-1}{4\sin{\frac{\pi}{n}}}$. Moreover, we have
$\lambda>\lambda_{1}$. Therefore
$\lambda>\dfrac{1}{1-4\sin{\frac{\pi}{n}}}\implies\dfrac{\lambda-1}{4\sin{\frac{\pi}{n}}}>\lambda$.
Hence, a counter-clockwise A-B path in any SMT of $\\{A_{i}\\}\cup\\{B_{i}\\}$
must have one edge greater than $\lambda$. This proves the claim.

Now, for any SMT of $\\{A_{i}\\}\cup\\{B_{i}\\}$, let $\mathcal{C}$ be a
counter-clockwise A-B path (this exists due to Lemma 3.12). From Claim 2, we
know that there is an edge $e$ in $\mathcal{C}$, with a length greater than
$\lambda$. On removing the edge $e$, the SMT splits into a forest of two
trees. Let the trees be $\mathcal{T}_{x}$ and $\mathcal{T}_{y}$. As we assumed
that there are two edges required to disconnect $\\{A_{i}\\}$ and
$\\{B_{i}\\}$, there must exist an A-B path in either $\mathcal{T}_{x}$ or
$\mathcal{T}_{y}$. Without loss of generality, let $\mathcal{T}_{x}$ contain
an A-B path, and hence $\mathcal{T}_{x}$ contains at least one point from
$\\{A_{i}\\}$ and at least one point from $\\{B_{i}\\}$. Further,
$\mathcal{T}_{y}$ must contain at least one terminal point (as it must contain
all terminal points in one of the sides of the removed edge $e$). If
$\mathcal{T}_{y}$ contains a point from $\\{A_{i}\\}$, then the polygon
$\\{A_{i}\\}$ has vertices both from $\mathcal{T}_{x}$ and $\mathcal{T}_{y}$;
otherwise, if $\mathcal{T}_{y}$ contains a point from $\\{B_{i}\\}$, then the
polygon $\\{B_{i}\\}$ has vertices both from $\mathcal{T}_{x}$ and
$\mathcal{T}_{y}$.

This means that either the polygon $\\{A_{i}\\}$ or the polygon $\\{B_{i}\\}$
will contain at least one node from each of $\mathcal{T}_{x}$ and
$\mathcal{T}_{y}$. Further, as any given vertex must be either in
$\mathcal{T}_{x}$ or in $\mathcal{T}_{y}$, either $\\{A_{i}\\}$ or
$\\{B_{i}\\}$ must contain two consecutive vertices $U_{i}$ and $U_{i+1}$ such
that one of them is in $\mathcal{T}_{x}$ and the other is in
$\mathcal{T}_{y}$. We simply connect $U_{i}$ and $U_{i+1}$ by the polygon edge
which is of length $1$ (if $U_{i},U_{i+1}\in\\{A_{i}\\}$) or of length
$\lambda$ (if $U_{i},U_{i+1}\in\\{B_{i}\\}$), giving us back a tree
$\mathcal{T}^{\prime}$containing all the terminals. However we discarded an
edge of length greater than $\lambda$ and added back an edge of length at most
$\lambda$ in this process, which means that the total length of
$\mathcal{T}^{\prime}$ is strictly less than the SMT we started with. This is
a contradiction.

We now proceed to further investigate the connectivity of $\\{A_{i}\\}$ and
$\\{B_{i}\\}$.

######  Lemma 3.17.

Consider an SMT for $\\{A_{i}\\}\cup\\{B_{i}\\}$ for $n\geq 13$ and
$\lambda\geq\lambda_{1}$. There must exist $j\in[n]$ and a Steiner point
$S_{1}$, such that terminals $A_{j},A_{j+1}$ form a path $A_{j}$, $S_{1}$,
$A_{j+1}$ in the SMT and each A-B path passes through $S_{1}$; where

$\lambda_{1}=\frac{1}{1-4\sin\frac{\pi}{n}}$

######  Proof 3.18.

From Lemma 3.12, we know that there exists one clockwise A-B path and one
counterclockwise A-B path in any SMT of $\\{A_{i}\\}\cup\\{B_{i}\\}$. Let a
clockwise A-B path start from $A_{r}$ and a counter-clockwise A-B path start
from $A_{l}$. Further following from Lemma 3.14, as there is one edge common
to all A-B paths, the clockwise A-B path from $A_{r}$ and the counter-
clockwise A-B path from $A_{l}$ must share a common edge $S_{1}S_{2}$.
Therefore, each A-B path must pass through $S_{1}$ and $S_{2}$. Without loss
of generality we assume that point $S_{1}$ is closer to the polygon
$\\{A_{i}\\}$ than $S_{2}$. This means $S_{1}$ is either a Stiener point or a
terminal vertex of $\\{A_{i}\\}$.

######  Claim 3.

$S_{1}$ is not a vertex in $\\{A_{i}\\}$

######  Proof 3.19.

For the sake of contradiction, we assume that $S_{1}$ to be a vertex in
$\\{A_{i}\\}$, let $S_{1}=A_{k}$ in some SMT $\mathcal{T}_{0}$. We disconnect
the edge $S_{1}S_{2}$ from $\mathcal{T}_{0}$, which results in the formation
of a forest of two trees $\mathcal{T}_{x}$ and $\mathcal{T}_{y}$ such that
$S_{1}=A_{k}\in\mathcal{T}_{x}$ and $S_{2}\in\mathcal{T}_{y}$.

$\mathcal{T}_{x}$ must contain all vertices of $\\{A_{i}\\}$ and
$\mathcal{T}_{y}$ must contain all vertices of $\\{B_{i}\\}$, as there would
be an A-B path in the graph otherwise (contradicting that $S_{1}S_{2}$
disconnects $\\{A_{i}\\}$ and $\\{B_{i}\\}$). We replace $\mathcal{T}_{x}$
with the SMT of $\\{A_{i}\\}$, which is also an MST (from [16]). Since all
MST’s are of the same length, we choose such an MST in which $A_{k}$ is not a
leaf node. This means $A_{k-1}A_{k}$ and $A_{k}A_{k+1}$ are edges in the
chosen MST of $\\{A_{i}\\}$. We now add back the edge $A_{k}S_{2}$, resulting
in a connected tree $\mathcal{T}_{0}^{\prime}$ of
$\\{A_{i}\\}\cup\\{B_{i}\\}$. Since we replaced the tree $\mathcal{T}_{x}$
with an SMT of $\\{A_{i}\\}$, the total length of the
$\mathcal{T}_{0}^{\prime}$ must not be more than the total length of the
$\mathcal{T}_{0}$.

However, we observe that $A_{k}$ has three neighbours in
$\mathcal{T}_{0}^{\prime}$, which are $A_{k+1},A_{k-1},S_{2}$. However $\angle
A_{k-1}A_{k}A_{k+1}>\frac{2\pi}{3}$. This means either $\angle
S_{2}A_{k}A_{k+1}<\frac{2\pi}{3}$ or $\angle
A_{k-1}A_{k}S_{2}<\frac{2\pi}{3}$. But due to Proposition 2.1, this cannot
form an SMT. Therefore $\mathcal{T}_{0}^{\prime}$ is not optimal; and hence,
$\mathcal{T}_{0}$ cannot be optimal as well. This proves the claim.

Therefore, $S_{1}$ must be a Steiner point. Let $P$ and $Q$ be the neighbours
of $S_{1}$ other than $S_{2}$, such that $\angle PS_{1}S_{2}$ is a clockwise
turn while $\angle QS_{1}S_{2}$ is a counter-clockwise turn. This means that
the clockwise A-B path from $A_{r}$ passes through $P$ and the counter-
clockwise A-B path from $A_{l}$ passes through $Q$. We prove that $P$ and $Q$
are consecutive vertices of $\\{A_{i}\\}$ in some SMT of
$\\{A_{i}\\}\cup\\{B_{i}\\}$.

######  Claim 4.

$P$ and $Q$ cannot simultaneously lie in the interior of the polygon
$\\{A_{i}\\}$.

######  Proof 3.20.

We assume for the sake of contradiction that both $P$ and $Q$ lie in the
interior of the polygon $\\{A_{i}\\}$. On deleting the edge $S_{1}S_{2}$, the
SMT of $\\{A_{i}\\}\cup\\{B_{i}\\}$ splits into two trees $\mathcal{T}_{1}$
(rooted at $S_{1}$) and $\mathcal{T}_{2}$ (rooted at $S_{2}$). Further, as all
A-B paths pass through $S_{1}S_{2}$, all vertices of $\\{A_{i}\\}$ must be in
$\mathcal{T}_{1}$ whereas all vertices of $\\{B_{i}\\}$ must lie in
$\mathcal{T}_{2}$. Further, $\mathcal{T}_{1}$ must be the SMT of
$\\{A_{i}\\}\cup\\{S_{1}\\}$ and $\mathcal{T}_{2}$ must be the SMT of
$\\{B_{i}\\}\cup\\{S_{2}\\}$.

  * •

Case I: One point in $\\{S_{1},S_{2}\\}$ lies in the interior of $\\{A_{i}\\}$
and the other point lies in the exterior of $\\{A_{i}\\}$: This means that the
edge $S_{1}S_{2}$ crosses some polygon edge of $\\{A_{i}\\}$, call it
$A_{m}A_{m+1}$. Let $D$ be the intersection of $A_{m}A_{m+1}$ and
$S_{1}S_{2}$. We replace $\mathcal{T}_{1}$ with an MST of $\\{A_{i}\\}$ that
contains the edge $A_{m}A_{m+1}$ (this can never lead to increase in total
tree length due to [16]) and remove the line segment $S_{1}D$ from
$\mathcal{T}_{2}$. This forms a tree connecting the terminal set
$\\{A_{i}\\}\cup\\{B_{i}\\}$ which has a total length smaller than the SMT we
started with, which is a contradiction.

  * •

Case II: Both $S_{1}$ and $S_{2}$ lie in the interior of polygon
$\\{A_{i}\\}$: We further consider two cases for this:

    * –

Consider that there is at least one polygon edge $A_{m}A_{m+1}$ of
$\\{A_{i}\\}$ such that it does not intersect with $\mathcal{T}_{2}$. Then we
can replace $\mathcal{T}_{1}$ by the MST of $\\{A_{i}\\}$ which does not
contain the edge $A_{m}A_{m+1}$ without reducing the total edge. However, this
will be a connecting tree of $\\{A_{i}\\}\cup\\{B_{i}\\}$ with a smaller total
length than the tree we started with (as we had removed the edge $S_{1}S_{2}$
previously), which is a contradiction.

    * –

Now, consider that all polygon edges of $\\{A_{i}\\}$ intersect with some edge
in $\mathcal{T}_{2}$. Since $\mathcal{T}_{2}$ is rooted at $S_{2}$ which lies
in the interior of $\\{A_{i}\\}$, there must be $n$ distinct edges crossing
the polygon $\\{A_{i}\\}$. However, $\mathcal{T}_{2}$ must be the SMT of the
points $\\{S_{2}\\}\cup\\{B_{i}\\}$, which means there can be at most $(n-1)$
Steiner points other than $S_{2}$ (from Proposition 2.1). Therefore, one of
these $n$ edges must have a point in $\\{B_{i}\\}$ as one of its endpoints,
contradicting Observation 3.3.

  * •

Case III: Both $S_{1}$ and $S_{2}$ lie in the exterior of polygon
$\\{A_{i}\\}$: This means that the edges $S_{1}P$ and $S_{1}Q$ intersect the
polygon edges of $\\{A_{i}\\}$. Further, from Observation 3.3, there cannot be
any terminal inside the triangle $S_{1}PQ$. Hence, $S_{1}P$ and $S_{1}Q$ must
intersect the same polygon edge of $\\{A_{i}\\}$ (otherwise intermediate
vertices from $\\{A_{i}\\}$ would lie in the triangle $S_{1}PQ$). Let this
edge be $A_{t}A_{t+1}$. Let $P_{1}$ and $Q_{1}$ be the points of intersection
of $A_{t}A_{t+1}$ with $S_{1}P$ and $S_{1}Q$ respectively.

We now remove the line segments $S_{1}P_{1}$ and $S_{1}Q_{1}$ from
$\mathcal{T}_{1}$. This results in another split into two connected trees
$\mathcal{T}_{P}$ (containing $P_{1}$, $P$ and a subset of $\\{A_{i}\\}$) and
$\mathcal{T}_{Q}$ (containing $Q_{1}$, $Q$ and the remaining vertices of
$\\{A_{i}\\}$).

We observe that the terminals in $\mathcal{T}_{P}$ and $\mathcal{T}_{Q}$ form
consecutive intervals of the edges in $\\{A_{i}\\}$. To see why, consider the
opposite, i.e. there are vertices $A_{i_{1}},A_{i_{2}},A_{i_{3}},A_{i_{4}}$
appearing in that order in $\\{A_{i}\\}$ such that
$A_{i_{1}},A_{i_{3}}\in\mathcal{T}_{P}$ whereas
$A_{i_{2}},A_{i_{4}}\in\mathcal{T}_{Q}$. As $\mathcal{T}_{P}$ and
$\mathcal{T}_{Q}$ lie in the interior of $\\{A_{i}\\}$, the path from
$A_{i_{1}}$ to $A_{i_{3}}$ in $\mathcal{T}_{P}$ must cross the path from
$A_{i_{2}}$ to $A_{i_{4}}$ in $\mathcal{T}_{Q}$. However, there cannot be
crossing paths in the original SMT of $\\{A_{i}\\}\cup\\{B_{i}\\}$ (due to
Proposition 2.1).

Let $\\{A_{w},A_{{w}+1},\ldots,A_{t}\\}$ be the terminals in $\mathcal{T}_{P}$
and the remaining terminals in $\\{A_{i}\\}$ are in $\mathcal{T}_{Q}$. Again,
let $\mathcal{T}_{P}^{\prime}$, $\mathcal{T}_{Q}^{\prime}$ be defined as:

$E(\mathcal{T}_{P}^{\prime})=\\{A_{w}A_{w+1},A_{w+1}A_{w+2},\ldots,A_{t-1}A_{t}\\}\cup\\{A_{t}P_{1}\\}$

and

$E(\mathcal{T}_{Q}^{\prime})=\\{A_{t+1}A_{t+2},\ldots,A_{w-2}A_{w-1}\\}\cup\\{Q_{1}A_{t-1}\\}$

From Observation 3.3, we know that $\mathcal{T}_{P}^{\prime}$ is the SMT of
$\\{A_{w},A_{{w}+1},\ldots,A_{t}\\}\cup\\{P_{1}\\}$ and
$\mathcal{T}_{Q}^{\prime}$ is the SMT of
$\\{A_{t+1},A_{{t}+2},\ldots,A_{w-1}\\}\cup\\{Q_{1}\\}$. Therefore,
$|\mathcal{T}_{P}^{\prime}|\leq|\mathcal{T}_{P}|$ and
$|\mathcal{T}_{Q}^{\prime}|\leq|\mathcal{T}_{Q}|$. This means that
$|\mathcal{T}_{1}|\geq|\mathcal{T}_{1}^{\prime}|$, where
$\mathcal{T}_{1}^{\prime}=\\{S_{1}P_{1},S_{1}Q_{1}\\}\cup\mathcal{T}_{P}^{\prime}\cup\mathcal{T}_{Q}^{\prime}$.
Further, $\mathcal{T}_{1}^{\prime}$ is also a connecting tree of
$\\{S_{1}\\}\cup\\{A_{i}\\}$ and as $\mathcal{T}_{1}$ is an SMT of
$\\{S_{1}\\}\cup\\{A_{i}\\}$, then $\mathcal{T}_{1}^{\prime}$ must also be an
SMT with $|\mathcal{T}_{1}^{\prime}|=|\mathcal{T}_{1}|$.

However, We can remove $S_{1}P_{1}$ and $P_{1}A_{t}$ from
$\mathcal{T}_{1}^{\prime}$ and add $S_{1}A_{t}$ to get another connecting tree
of $\\{S_{1}\\}\cup\\{A_{i}\\}$, but with shorter total length (as
$\overline{S_{1}P_{1}}+\overline{P_{1}A_{t}}>\overline{S_{1}A_{t}}$ from
triangle inequality). This contradicts the optimality of
$\mathcal{T}_{1}^{\prime}$ which was derived to be an SMT of
$\\{S_{1}\\}\cup\\{A_{i}\\}$.

This proves the claim.

We proceed to prove a stronger claim regarding $P$ and $Q$.

######  Claim 5.

$P$ and $Q$ are consecutive vertices of $\\{A_{i}\\}$ in any SMT of
$\\{A_{i}\\}\cup\\{B_{i}\\}$.

######  Proof 3.21.

We first prove that $P,Q$ are vertices of $\\{A_{i}\\}$.

From Claim 4, we know that at least one among $P$ and $Q$ must not be in the
interior of polygon $\\{A_{i}\\}$. Without loss of generality, let it be $P$.
We now show that $P$ is a vertex of $\\{A_{i}\\}$. For the sake of
contradiction we assume that $P$ is not a vertex of $\\{A_{i}\\}$ i.e. $P$ is
a Steiner point. Let $\overrightarrow{PF_{1}}$ and $\overrightarrow{PF_{2}}$
be tangents from $P$ to $\\{A_{i}\\}$ where $F_{1},F_{2}$ are the points of
tangency on $\\{A_{i}\\}$. As $\overrightarrow{PF_{1}}$ and
$\overrightarrow{PF_{2}}$ are tangents, $\angle F_{1}PF_{2}<\pi$. We denote
the region between the tangents $\overrightarrow{PF_{1}}$ and
$\overrightarrow{PF_{2}}$ which contains the all the points in $\\{A_{i}\\}$
as $\mathcal{R}$.

From any Steiner point $H$, which lies outside $\mathcal{R}$, we can choose a
neighbour $H_{1}$ of $H$ such that $\overrightarrow{HH_{1}}$ is not directed
towards $\mathcal{R}$. Further we now show that there is one neighbour $P_{1}$
of $P$ such that $P_{1}$ is not in $\mathcal{R}$ and $P_{1}\neq S_{1}$.

Case I: $S_{1}$ lies in $\mathcal{R}$. However there must be another neighbour
$P_{1}$ of $P$ not in $\mathcal{R}$ (as $\angle F_{1}PF_{2}<\pi$) but as
$P_{1}$ is outside $\mathcal{R}$, we must have $P_{1}\neq S_{1}$.

Case II: $S_{1}$ does not lie in $\mathcal{R}$ (Figure 8). As the counter-
clockwise A-B path from $A_{l}$ passes through $Q$, $A_{l}$ must be to the
left of the line $L_{QS_{1}}$ if the line is given a orientation from $Q$ to
$S_{1}$. This means that one of the tangents from $P$ (Without loss of
generality assume it to be $\overrightarrow{PF_{1}}$) intersects with the line
$L_{QS_{1}}$. Therefore, taking angles in counter-clockwise order, we have:

Figure 8: Case II of 5

$\displaystyle\angle S_{1}PF_{1}<\frac{\pi}{3}$ $\displaystyle[\text{as
}\overrightarrow{PF_{1}}\text{ intersects }L_{QS_{1}}]$
$\displaystyle\implies$ $\displaystyle\angle S_{1}PF_{2}=\angle
S_{1}PF_{1}+\angle F_{1}PF_{2}<\frac{\pi}{3}+\pi=\frac{4\pi}{3}$
$\displaystyle\implies$ $\displaystyle\angle F_{2}PS_{1}=2\pi-\angle
S_{1}PF_{2}>2\pi-\frac{4\pi}{3}=\frac{2\pi}{3}$

Hence there must exist one neighbour $P_{1}$ of $P$ lying outside the
$\mathcal{R}$, precisely in the region bounded by the rays
$\overrightarrow{PF_{2}}$ and $\overrightarrow{PS_{1}}$ with $P_{1}\neq
S_{1}$.

Further we can choose a neighbour $P_{2}$ of $P_{1}$ such that
$\overrightarrow{P_{1}P_{2}}$ is directed away from $\mathcal{R}$. We can
continue choosing $P_{2},P_{3},\ldots$ such that
$\overrightarrow{P_{i}P_{i+1}}$ is directed away from the region
$\mathcal{R}$. Moreover, the path $P,P_{1},P_{2},\ldots$ must end at some
point $B_{k}$ as it cannot end in any vertex of $\\{A_{i}\\}$ (since all
vertices of $\\{A_{i}\\}$ are in $\mathcal{R}$). Now, let $\mathcal{C}_{1}$ be
the path from $A_{r}$ to $B_{k}$ (which passes through $P$ and $P_{1}$) and
let $\mathcal{C}_{2}$ be the counter-clockwise A-B path from $A_{l}$ (passing
through $Q$, $S_{1}$ and $S_{2}$). We observe that $\mathcal{C}_{1}$ and
$\mathcal{C}_{2}$ are two edge disjoint A-B paths, which is a contradiction to
Lemma 3.14. This proves that $P$ is indeed a vertex in $\\{A_{i}\\}$.
Therefore by Claim 4, $Q$ does not lie inside $\\{A_{i}\\}$ and repeating this
same argument on $Q$ yields that $Q$ is also a vertex of $\\{A_{i}\\}$.

Now, to prove that $P$ and $Q$ are consecutive vertices of $\\{A_{i}\\}$, we
use Observation 3.3. Observation 3.3 implies that there must not be any other
point of the SMT in the triangle $PS_{1}Q$. This means that $P$ and $Q$ must
be consecutive vertices of $\\{A_{i}\\}$, otherwise all polygon vertices of
$\\{A_{i}\\}$ occurring in between $P$ and $Q$ would be inside the triangle
$PS_{1}Q$ (as $\angle PS_{1}Q=\dfrac{2\pi}{3}$ and $n\geq 13$). This proves
the claim.

Therefore, $P$ and $Q$ are consecutive vertices $A_{j},A_{j+1}$ of the polygon
$\\{A_{i}\\}$, for some $j\in[n]$ such that $A_{j}$, $S_{1}$, $A_{j+1}$ is a
path in the SMT, where $S_{1}$ is a Steiner point lying on all A-B paths.

Our next step is to investigate some more structural properties of an SMT for
$\\{A_{i}\\}\cup\\{B_{i}\\}$. From [5], we may guess that there would be a lot
of polygon edges of both $\\{A_{i}\\}$ and $\\{B_{i}\\}$ in an SMT. We prove
the following Lemma, stating that there is an SMT of
$\\{A_{i}\\}\cup\\{B_{i}\\}$ which contains $(n-2)$ polygon edges of
$\\{A_{i}\\}$.

######  Lemma 3.22.

For an SMT for $\\{A_{i}\\}\cup\\{B_{i}\\}$ with aspect ratio $\lambda$,
$\lambda>\lambda_{1}=\frac{1}{1-4\sin\frac{\pi}{n}}$, let $S_{1}$ be the
Steiner point such that all A-B paths pass through $S_{1}$. Let $A_{j}$ and
$A_{j+1}$ be vertices of $\\{A_{i}\\}$ which are connected to $S_{1}$. Then,
there exists an SMT of $\\{A_{i}\\}\cup\\{B_{i}\\}$ having $(n-2)$ polygon
edges of $\\{A_{i}\\}$ other than $A_{j}A_{j+1}$.

######  Proof 3.23.

Let $\mathcal{T}_{0}$ be any SMT of $\\{A_{i}\\}\cup\\{B_{i}\\}$. From Lemma
3.17, we know that there exists $S_{1}$, $A_{j}$ and $A_{j+1}$ such that
$S_{1}$ is a Steiner point which is a part of all A-B paths, and
$A_{j}S_{1}A_{j+1}$ is a path $\mathcal{T}_{0}$.

From $\mathcal{T}_{0}$, we remove the edges $S_{1}A_{j}$ and $S_{1}A_{j+1}$
and add the edge $A_{j}A_{j+1}$. This results in a forest of two disjoint
trees $\mathcal{T}_{x}$ and $\mathcal{T}_{y}$. One of these trees (say
$\mathcal{T}_{x}$) must contain all terminal points from $\\{A_{i}\\}$ and the
other tree must contain all terminals from $\\{B_{i}\\}$, as no more A-B paths
exist after we removed the edges $S_{1}A_{j}$ and $S_{1}A_{j+1}$. Therefore we
have
$|\mathcal{T}_{0}|=|\mathcal{T}_{x}|+|\mathcal{T}_{y}|-1+\overline{S_{1}A_{j}}+\overline{S_{1}A_{j+1}}$.

We further replace $\mathcal{T}_{x}$ with a Euclidean minimum spanning tree
$\mathcal{T}_{x}^{\prime}$ of $\\{A_{i}\\}$ such that the edge $A_{j}A_{j+1}$
is present in $\mathcal{T}_{x}^{\prime}$. From [5], we know that
$|\mathcal{T}_{x}^{\prime}|\leq|\mathcal{T}_{x}|$. We now remove the edge
$A_{j}A_{j+1}$ and add back the edges $S_{1}A_{j}$ and $S_{1}A_{j+1}$ which
gives a connected tree $\mathcal{T}_{0}^{\prime}$ of
$\\{A_{i}\\}\cup\\{B_{i}\\}$. Therefore we have:

$|\mathcal{T}_{0}^{\prime}|=|\mathcal{T}_{x}^{\prime}|+|\mathcal{T}_{y}|-1+\overline{S_{1}A_{j}}+\overline{S_{1}A_{j+1}}\leq|\mathcal{T}_{x}|+|\mathcal{T}_{y}|-1+\overline{S_{1}A_{j}}+\overline{S_{1}A_{j+1}}=|\mathcal{T}_{0}|$

This means $\mathcal{T}_{0}^{\prime}$ must be an SMT. However, all polygon
edges of polygon $\\{A_{i}\\}$ appearing in $\mathcal{T}_{x}^{\prime}$ also
appear in $\mathcal{T}_{0}^{\prime}$ as well, except $A_{j}A_{j+1}$.
Therefore, the SMT $\mathcal{T}_{0}^{\prime}$ has $(n-2)$ polygon edges of the
polygon $\\{A_{i}\\}$.

With these set of results in hand, we can now show that there exists an SMT of
$\\{A_{i}\\}\cup\\{B_{i}\\}$ following a _singly connected topology_. To show
this, we start with any SMT for $\\{A_{i}\\}\cup\\{B_{i}\\}$ ,
$\mathcal{T}_{0}$, that satisfies all the results derived so far and transform
it into a Steiner tree of _singly connected topology_ having total length not
longer than the initial Steiner tree $\mathcal{T}_{0}$.

######  Theorem 3.24.

There exists an SMT for $\\{A_{i}\\}\cup\\{B_{i}\\}$ following a singly
connected topology for $n\geq 13$ and $\lambda\geq\lambda_{1}$, where

$\lambda_{1}=\frac{1}{1-4\sin\frac{\pi}{n}}$

######  Proof 3.25.

Let $\mathcal{T}_{0}$ be any SMT of $\\{A_{i}\\}\cup\\{B_{i}\\}$ which
satisfies the properties of Lemma 3.22. Further, from Lemma 3.17, there is a
Steiner point $S_{1}$ which lies on all A-B paths, and there are two
consecutive vertices $A_{j}$, $A_{j+1}$ such that $A_{j}$, $S_{1}$, $A_{j+1}$
is a path in $\mathcal{T}_{0}$. As $\mathcal{T}_{0}$ satisfies the property of
Lemma 3.22, $\mathcal{T}_{0}$ has $(n-2)$ polygon edges of $\\{A_{i}\\}$
excluding the edge $A_{j}A_{j+1}$.

Let $H$ be the point in the interior of the polygon $\\{A_{i}\\}$ such that
$HA_{j}A_{j+1}$ form an equilateral triangle. As $n>6$, the common centre $O$
of $\\{A_{i}\\}$ and $\\{B_{i}\\}$ does not lie inside the triangle
$HA_{j}A_{j+1}$. Now, we modify $\mathcal{T}_{0}$ as follows:

  1. 1.

Remove edges $A_{j}S_{1}$, $S_{1}A_{j+1}$ and add edge $S_{1}H$ to get the
forest $\mathcal{T}_{1}$. We know from [9] that $S_{1}$, $S_{2}$ and $H$ are
collinear and this transformation does not change the total length. Therefore
$|\mathcal{T}_{0}|=|\mathcal{T}_{1}|$. Here, $|\mathcal{T}_{1}|$ denotes the
sum of the lengths of edges present in $\mathcal{T}_{1}$.

  2. 2.

Add edge $HO$ and remove all polygon edges of $\\{A_{i}\\}$ to get
$\mathcal{T}_{2}$. Therefore
$|\mathcal{T}_{2}|=|\mathcal{T}_{1}|+\overline{HO}-(n-2)=|\mathcal{T}_{0}|+\overline{HO}-(n-2)$.
We observe that $\mathcal{T}_{2}$ is a tree connecting the points in
$\\{B_{i}\\}\cup\\{O\\}$.

  3. 3.

Let $S_{0}$ be the Torricelli point of the triangle $OB_{j}B_{j+1}$. Let
$\mathcal{T}_{3}$ be the Steiner tree of $\\{B_{i}\\}\cup\\{O\\}$ with edges
$S_{0}O$, $S_{0}B_{j}$, $S_{0}B_{j+1}$ and other points in $\\{B_{i}\\}$
connected through $(n-2)$ polygon edges of the polygon $\\{B_{i}\\}$. From
[16], we know that $\mathcal{T}_{3}$ is the SMT of $\\{B_{i}\\}\cup\\{O\\}$.
Therefore
$|\mathcal{T}_{3}|\leq|\mathcal{T}_{2}|=|\mathcal{T}_{0}|+\overline{HO}-(n-2)$.
Further we know that $H$ lies on the edge $OS_{0}$ (as $O$, $S_{0}$ and $H$
lie on the perpendicular bisector of $B_{j}$ and $B_{j+1}$).

  4. 4.

Remove edge $S_{0}O$ and add edge $S_{0}H$ to get $\mathcal{T}_{4}$. As $H$
lies on the edge $OS_{0}$, we have
$|\mathcal{T}_{4}|=|\mathcal{T}_{3}|-\overline{OH}\leq|\mathcal{T}_{0}|-(n-2)$.

  5. 5.

Let $S_{3}$ be the intersection of the circumcircle of triangle
$A_{j}HA_{j+1}$ (from Lemma 3.1 the intersection exists as
$\lambda_{1}\geq\lambda_{v}$ for $n\geq 13$). Remove the edge $S_{3}H$ and add
the edges $S_{3}A_{j}$ and $S_{3}A_{j+1}$ to get $\mathcal{T}_{5}$. Again,
from [9] we know that this transformation does not change the total length.
Hence $|\mathcal{T}_{5}|=|\mathcal{T}_{5}|\leq|\mathcal{T}_{0}|-(n-2)$.
Moreover, as $\lambda>\lambda_{v}$, we observe that
$\\{A_{j},B_{j},A_{j+1},B_{j+1},S_{3},S_{0}\\}$ form the vertices of the
vertical gadget and points $O$, $H$, $S_{3}$, $S_{0}$ appear in that order on
the perpendicular bisector of $B_{j}$ and $B_{j+1}$.

  6. 6.

Add back the $(n-2)$ polygon edges of $\\{A_{i}\\}$ which were removed in the
second step to get $\mathcal{T}_{6}$. Therefore
$|\mathcal{T}_{4}|=|\mathcal{T}_{5}|+(n-2)\leq|\mathcal{T}_{0}|$. We further
observe that $\mathcal{T}_{6}$ is a Steiner tree connecting the points
$\\{A_{i}\\}\cup\\{B_{i}\\}$ with a singly connected topology.

Therefore we started with an arbitrary SMT $\mathcal{T}_{0}$ and transformed
it into a Steiner tree $\mathcal{T}_{6}$ with a singly connected topology
(where $\\{A_{j},B_{j},A_{j+1},B_{j+1},S_{3},S_{0}\\}$ form the vertices of
the vertical gadget) which has a total length not worse than
$\mathcal{T}_{0}$. Hence $\mathcal{T}_{6}$ must be an SMT of
$\\{A_{i}\\}\cup\\{B_{i}\\}$. This proves the theorem.

######  Remark 3.26.

Theorem 3.24 determines the exact structure of the SMT for
$\\{A_{i}\\}\cup\\{B_{i}\\}$ . Further from Section 3.1 we determine the exact
method to construct the two additional Steiner points in $\mathcal{O}(1)$
steps - note that this construction time is independent of the integer $n$ or
the real number $\lambda$. Therefore, SMT for $\\{A_{i}\\}\cup\\{B_{i}\\}$ for
$n\geq 13$ and $\lambda\geq\lambda_{1}$ is solvable in polynomial time.

Note that the total length of any SMT for $\\{A_{i}\\}\cup\\{B_{i}\\}$ , when
$n\geq 13$ and $\lambda\geq\lambda_{1}$, is

$\displaystyle|\mathcal{T}_{6}|=|\text{vertical gadget}|+|(n-2)\text{ edges of
$\\{B_{i}\\}$}|+|(n-2)\text{ edges of $\\{A_{i}\\}$}|$ $\displaystyle\implies$
$\displaystyle|\mathcal{T}_{6}|=\bigg{(}\dfrac{(\lambda-1)}{2\tan\frac{\pi}{n}}+\dfrac{\sqrt{3}(\lambda+1)}{2}\bigg{)}+(n-2)\cdot\lambda+(n-2)$
$\displaystyle\implies$
$\displaystyle{|\mathcal{T}_{6}|=\dfrac{(\lambda-1)}{2\tan\frac{\pi}{n}}+\bigg{(}n-2+\frac{\sqrt{3}}{2}\bigg{)}(\lambda+1)}$

Further, $\lambda_{1}$ converges to 1 very quickly with increasing $n$
(plotted in Figure 9):

$n$ | 13 | 20 | 40 | 100 | 500
---|---|---|---|---|---
$\lambda_{1}$ | 23.3987 | 2.6719 | 1.4574 | 1.1437 | 1.0258

Figure 9: Plot of $\lambda_{1}$ & $\lambda_{v}$ against $n$

This means for large sized $n$ and for ratios that are not too small, the SMT
will follow a singly connected topology.

##  4 on $f(n)$-Almost Convex Point Sets

In this section, we design an exact algorithm for on $f(n)$-Almost Convex
Point Sets running in time $2^{\mathcal{O}(f(n)\log n)}$. Note that $f(n)\leq
n$ is always true. Therefore, we are given as input a set $\mathcal{P}$ of $n$
points in the Euclidean Plane such that $\mathcal{P}$ can be partitioned as
$\mathcal{P}=\mathcal{P}_{1}\uplus\mathcal{P}_{2}$, where $\mathcal{P}_{1}$ is
the convex hull of $\mathcal{P}$ and $|\mathcal{P}_{2}|=f(n)$.

First, we look into some mathematical results and computational results to
finally arrive at the algorithm for solving on $f(n)$-Almost Convex Point
Sets.

We know that the SMT of $\mathcal{P}$ can be decomposed uniquely into one or
more full Steiner subtrees, such that two full Steiner subtrees share at most
one node [9]. In the following lemma, we further characterize one full Steiner
subtree.

######  Lemma 4.1.

Let $\mathbb{F}$ be the full Steiner decomposition of an SMT of $\mathcal{P}$.
Then there exists a full Steiner subtree $\mathcal{F}\in\mathbb{F}$ such that
$\mathcal{F}$ has at most one common node with at most one other full Steiner
subtree in $\mathbb{F}$.

######  Proof 4.2.

If the SMT of $\mathcal{P}$ is a full Steiner tree, then the statement is
trivially true.

Otherwise, we assume that the SMT of $\mathcal{P}$ has full Steiner subtrees,
$\mathbb{F}=\\{\mathcal{F}_{1},\mathcal{F}_{2},\ldots,\mathcal{F}_{m}\\}$,
$m\geq 2$. Now, for the sake of contradiction, we assume that for each full
Steiner subtree $\mathcal{F}_{j}$ there are atleast two other full Steiner
subtrees ${\sf Neitree}(\mathcal{F}_{j})^{1},{\sf
Neitree}(\mathcal{F}_{j})^{2}\in\mathbb{F}$ and two terminals
$P_{1}(\mathcal{F}_{j}),P_{2}(\mathcal{F}_{j})\in\mathcal{P}$ such that
$P_{i}(\mathcal{F}_{j})\in V(\mathcal{F}_{j})\cap V({\sf
Neitree}(\mathcal{F}_{j})^{i})$, $i\in\\{1,2\\}$. Now, let us construct a walk
$W$ in the SMT of $\mathcal{P}$. Starting from $P_{1}(\mathcal{F}_{1})$ of the
full Steiner subtree $\mathcal{F}_{1}\in\mathbb{F}$, we include the path in
$\mathcal{F}_{1}$ connecting to $P_{2}(\mathcal{F}_{1})$. Note that
$P_{2}(\mathcal{F}_{1})$ is also contained in ${\sf
Neitree}(\mathcal{F}_{1})^{2}$. Let ${\sf
Neitree}(\mathcal{F}_{1})^{2}=\mathcal{F}_{w_{1}}$ for some
$w_{1}\in[m],w_{1}\neq 1$. Also let
$P_{2}(\mathcal{F}_{1})=P_{1}(\mathcal{F}_{w_{1}})$. Then, we know that there
is a $P_{2}(\mathcal{F}_{w_{1}})$. In $W$, we include the path in
$\mathcal{F}_{w_{1}}$ connecting $P_{1}(\mathcal{F}_{w_{1}})$ to
$P_{2}(\mathcal{F}_{w_{1}})$. In general, suppose the $i^{th}$ full Steiner
subtree to be considered in building the walk is $\mathcal{F}_{w_{i-1}}$ which
was reached via point $P_{1}(\mathcal{F}_{w_{i-1}})$. Then we include in $W$
the path in $\mathcal{F}_{w_{i-1}}$ connecting $P_{1}(\mathcal{F}_{w_{i-1}})$
and $P_{2}(\mathcal{F}_{w_{i-1}})$. Thus, we can indefinitely keep
constructing the walk $W$ as for each $\mathcal{F}_{w_{i-1}}$ both
$P_{1}(\mathcal{F}_{w_{i-1}}),P_{2}(\mathcal{F}_{w_{i-1}})$ always exist.
However, since there are $m$ full Steiner subtrees this means that there is an
$\mathcal{F}_{k}\in\mathbb{F}$ and two indices $i\neq j$ such that
$\mathcal{F}_{k}=\mathcal{F}_{w_{i}}=\mathcal{F}_{w_{j}}$. Thus, there exists
a cycle in $W$, which implies that there is a cycle in the SMT of
$\mathcal{P}$ (contradiction). Therefore, there must be at least one full
Steiner subtree that has at most one common terminal with at most one other
full Steiner subtree.

######  Remark 4.3.

A full Steiner subtree of the SMT of $\mathcal{P}$ has the topology of a tree.
Thus, from Lemma 4.1, we conclude that a full Steiner subtree, that has at
most one common terminal with at most one other full Steiner subtree, has at
least one leaf of the SMT.

######  Definition 4.4.

Let the full Steiner subtrees, that have at most one terminal shared with at
most one other full Steiner subtree, be called leaf full Steiner subtrees. Let
the terminal which is shared be called the pivot of the leaf full Steiner
subtree.

(a)

(b)

Figure 10: Leaf full Steiner subtrees enclosed in ellipses, other full Steiner
subtrees enclosed in rectangles, pivots of leaf full Steiner subtrees
encircled

######  Lemma 4.5.

Let $\mathcal{F}$ be a leaf full Steiner Subtree of the SMT of $\mathcal{P}$,
with terminal points $\mathcal{P}_{\mathcal{\mathcal{F}}}\subseteq\mathcal{P}$
and having pivot $P_{\mathcal{F}}$. Deleting
$\mathcal{F}\setminus\\{P_{\mathcal{F}}\\}$ from the SMT of $\mathcal{P}$
gives us an SMT of the terminal points
$((\mathcal{P}-\mathcal{P}_{\mathcal{F}})\cup\\{P_{\mathcal{F}}\\})$.

######  Proof 4.6.

Firstly, we observe that deleting $\mathcal{F}\setminus\\{P_{\mathcal{F}}\\}$
from the SMT of $\mathcal{P}$ will indeed give us a tree, as $\mathcal{F}$ is
a leaf full Steiner subtree. Let us call this tree $\mathcal{Y}$.

Now for the sake of contradiction, we assume that the total length of
$\mathcal{Y}$ is strictly larger than the SMT $\mathcal{F}^{\prime}$ of
$((\mathcal{P}-\mathcal{P}_{\mathcal{F}})\cup\\{P_{\mathcal{F}}\\})$. However,
this means, the total length of $\mathcal{F}^{\prime}\cup\mathcal{F}$ is
strictly smaller than that of the SMT of $\mathcal{P}$. As
$\mathcal{F}^{\prime}\cup\mathcal{F}$ is also a Steiner tree of $\mathcal{P}$,
this contradicts the minimality of the initial SMT of $\mathcal{P}$.

Now we are ready to describe the algorithm. Recall that $\mathcal{P}$ is
partitioned as $\mathcal{P}=\mathcal{P}_{1}\uplus\mathcal{P}_{2}$, where
$\mathcal{P}_{1}$ is the convex hull of $\mathcal{P}$ and $\mathcal{P}_{2}$ is
the set of $f(n)$ points lying in the interior of $\mathcal{P}_{1}$. For the
sake of brevity of notations let $|\mathcal{P}_{2}|=k$.

######  Lemma 4.7.

Let $\mathcal{P}$ be a $k$-Almost Convex Point Set. A minimum FST of a subset
$\mathcal{S}$ of $\mathcal{P}$ can be found in
$\mathcal{O}(4^{|{\mathcal{S}}|}\cdot|\mathcal{S}|^{k})$ time.

######  Proof 4.8.

We observe that for any $\mathcal{S}\subseteq\mathcal{P}$, $\mathcal{S}$ forms
a convex polygon with at most $k$ points lying in the interior. For
$|{\mathcal{S}}|\leq 2$, the statement of the lemma is trivially true. Hence
we assume that $|{\mathcal{S}}|>2$.

From [9], the number of full Steiner topologies of $\mathcal{S}$ is

$\frac{|\mathcal{S}|!}{|\mathrm{CH}(\mathcal{S})|!}\cdot\frac{\binom{2|{\mathcal{S}}|-4}{|{\mathcal{S}}|-2}}{|{\mathcal{S}}|-1}$

However, we know that:

$\frac{\binom{2|{\mathcal{S}}|-4}{|{\mathcal{S}}|-2}}{|{\mathcal{S}}|-1}<\frac{\binom{2|{\mathcal{S}}|}{|{\mathcal{S}}|}}{|{\mathcal{S}}|}<\frac{\sum\limits_{r=0}^{2|{\mathcal{S}}|}\binom{2|{\mathcal{S}}|}{k}}{|{\mathcal{S}}|}=\frac{2^{2|{\mathcal{S}}|}}{|{\mathcal{S}}|}=\frac{4^{|{\mathcal{S}}|}}{|{\mathcal{S}}|}$

And,

$\frac{|\mathcal{S}|!}{|\mathrm{CH}(\mathcal{S})|!}<\frac{|\mathcal{S}|!}{(|\mathcal{S}|-k)!}<|\mathcal{S}|^{k}$

Therefore, the number of full Steiner topologies of $\mathcal{S}$ is at most
$4^{|{\mathcal{S}}|}|\mathcal{S}|^{k-1}$. Each of these topologies can be
enumerated and using _Melzak’s FST Algorithm_ , we can also find the SMT
realizing each such full Steiner topology in linear time, as given in [9].
Therefore to iterate over all topologies and find a minimum takes at most
time:

$(4^{|{\mathcal{S}}|}\cdot|\mathcal{S}|^{k-1})\cdot\mathcal{O}(|\mathcal{S}|)=\mathcal{\mathcal{missing}}O(4^{|{\mathcal{S}}|}\cdot|\mathcal{S}|^{k})$

Now, we find the time required for extending the results of Lemma 4.7 to all
subsets of $\mathcal{P}$.

######  Lemma 4.9.

Let $\mathcal{P}$ be a $k$-Almost Convex Set. Computing a minimum FST for all
subsets $\mathcal{S}\subseteq\mathcal{P}$ can be done in
$\mathcal{O}(n^{k}\cdot 5^{n})$ time.

######  Proof 4.10.

Using Lemma 4.7, we can get a minimum FST for a single subset
$\mathcal{S}\subseteq\mathcal{P}$ in
$\mathcal{O}(4^{|{\mathcal{S}}|}|\mathcal{S}|^{k})$ time. Moreover, we know
that the number of subsets of $\mathcal{P}$ that are of size $r$ is
$\binom{n}{r}$. This means that the total time to compute a minimum FST for
all subsets $\mathcal{S}\subseteq\mathcal{P}$, time taken is:

$\sum\limits_{r=0}^{n}\binom{n}{r}\cdot\mathcal{O}(4^{r}\cdot
r^{k})=\sum\limits_{r=0}^{n}\binom{n}{r}\cdot\mathcal{O}(n^{k}\cdot
4^{r})=\mathcal{O}(n^{k}\cdot(1+4)^{n})=\mathcal{O}(n^{k}\cdot 5^{n})$

For each $\mathcal{S}\subseteq\mathcal{P}$, we denote by
$\mathcal{F}_{\mathcal{S}}$ a minimum FST of $\mathcal{S}$ and by
$\mathcal{T}_{\mathcal{S}}$ the SMT of $\mathcal{S}$.

######  Lemma 4.11.

The SMT of subset $\mathcal{S}\subseteq\mathcal{P}$,
$\mathcal{T}_{\mathcal{S}}$, can be found in $\mathcal{O}(|{\mathcal{S}}|\cdot
2^{|{\mathcal{S}}|})$ time, given that we have pre-computed
$\mathcal{T}_{\mathcal{R}}$ and $\mathcal{F}_{\mathcal{R}}$,
$\forall\mathcal{R}\subseteq\mathcal{S}$.

######  Proof 4.12.

If $\mathcal{T}_{\mathcal{S}}$ was a full Steiner tree then it would be
$\mathcal{F}_{\mathcal{S}}$. Otherwise, $\mathcal{T}_{\mathcal{S}}$ contains
multiple full Steiner subtrees.

Let $\mathcal{F}$ be a leaf full Steiner subtree of
$\mathcal{T}_{\mathcal{S}}$ with pivot $P_{\mathcal{F}}$. Therefore from Lemma
4.5 we have
$\mathcal{T}_{\mathcal{S}}=\mathcal{T}_{((\mathcal{S}-V(\mathcal{F}))\cup\\{P_{\mathcal{F}}\\})}\cup\mathcal{F}$.
Therefore we can iterate over all subsets $\mathcal{R}\subset\mathcal{S}$ and
all terminals $P\in\mathcal{R}$, and take the minimum-length tree among
$\mathcal{T}_{((\mathcal{S}-\mathcal{R})\cup\\{P\\})}\cup\mathcal{F}_{\mathcal{R}}$.
Since we are iterating over all $\mathcal{R}\subset\mathcal{S}$, and all
$P\in\mathcal{R}$, we are guaranteed to get
$\mathcal{R}=V(\mathcal{F})\cap\mathcal{S}$ and $P=P_{\mathcal{F}}$ on one
such iteration.

Now, as there are $\mathcal{O}(2^{|\mathcal{S}|})$ possibilities of
$\mathcal{R}\subset\mathcal{S}$ and $\mathcal{O}(|\mathcal{S}|)$ possibilities
of $P\in\mathcal{R}$, we have $\mathcal{O}(|S|\cdot 2^{|\mathcal{S}|})$
possibilities of the pair $(\mathcal{R},P)$. Therefore the total time required
for iterating is $\mathcal{O}(|{\mathcal{S}}|\cdot 2^{|{\mathcal{S}}|})$.

######  Lemma 4.13.

SMTs for all subsets $\mathcal{S}\subseteq\mathcal{P}$,
$\mathcal{T}_{\mathcal{S}}$ can be found in $\mathcal{O}(n\cdot 3^{n})$ time,
given that we have precomputed a minimum FST $\mathcal{F}_{\mathcal{S}}$
$\forall\mathcal{S}\subseteq\mathcal{P}$.

######  Proof 4.14.

Using Lemma 4.11, we can get the SMT $\mathcal{T}_{\mathcal{S}}$, for a single
subset $\mathcal{S}\subseteq\mathcal{P}$ in $\mathcal{O}(r\cdot 2^{r})$ time,
where $|{\mathcal{S}}|=r$. Moreover, we know that the number of subsets of
$\mathcal{P}$ that are of size $r$ is $\binom{n}{r}$. This means that the
total time to compute the SMT for all subsets
$\mathcal{S}\subseteq\mathcal{P}$, time taken is:

$\sum\limits_{k=0}^{n}\binom{n}{k}\cdot\mathcal{O}(k\cdot
2^{k})=\mathcal{O}(n\cdot(1+2)^{n})=\mathcal{O}(n\cdot 3^{n})$

However, to apply Lemma 4.11 on some subset $\mathcal{S}\subseteq\mathcal{P}$
for computing $\mathcal{T}_{\mathcal{S}}$, we must also have
$\mathcal{T}_{\mathcal{R}}$ precomputed for all
$\mathcal{R}\subseteq\mathcal{S}$. This can be guaranteed by computing
$\mathcal{T}_{\mathcal{S}}$ and $\mathcal{F}_{\mathcal{S}}$, for all subsets
$\mathcal{S}\subseteq\mathcal{P}$ in an increasing order of $|\mathcal{S}|$
(or any order which guarantees that the subsets of $\mathcal{S}$ are processed
before $\mathcal{S}$).

Finally, we state our algorithm.

######  Theorem 4.15.

An SMT $\mathcal{T}_{\mathcal{P}}$ of a $k$-Almost Convex Set $\mathcal{P}$ of
terminals can be computed in $\mathcal{O}(n^{k}\cdot 5^{n})$ time.

######  Proof 4.16.

Consider the following algorithm:

Algorithm 1 Computation of $\mathcal{T_{P}}$ Input: $\mathcal{P}$

1:for all $\mathcal{S}\subseteq\mathcal{P}$ do

2: Compute $\mathcal{F_{S}}$ $\triangleright$ Using Lemma 4.9

3:end for$\triangleright$ This takes $\mathcal{O}(n^{k}\cdot 5^{n})$ time

4:for all $\mathcal{S}\subseteq\mathcal{P}$ do

5: Compute $\mathcal{T_{S}}$ $\triangleright$ Using Lemma 4.13

6:end for$\triangleright$ This takes $\mathcal{O}(n\cdot 3^{n})$ time

7:return $\mathcal{T_{P}}$ $\triangleright$ Total runtime is
$\mathcal{O}(n^{k}\cdot 5^{n}+n\cdot 3^{n})=\mathcal{O}(n^{k}\cdot 5^{n})$

Hence we have an SMT of a $k$-Almost Convex Point Set $\mathcal{P}$ in
$\mathcal{O}(n^{k}\cdot 5^{n})$ time.

The above theorem gives us several improvements in special classes of inputs,
based on the number of input points lying inside the convex hull of the input
set, as described in the following corollary. Let there be an $f(n)$-Almost
Convex Point Set $\mathcal{P}$ containing $n$ points. Recall that
$\mathcal{P}=\mathcal{P}_{1}\uplus\mathcal{P}_{2}$, $\mathcal{P}_{1}$
containing the points on the convex hull of $\mathcal{P}$, and
$|\mathcal{P}_{2}|=f(n)$. It is only possible that $f(n)\leq n$.

######  Corollary 4.17.

Let $\mathcal{P}$ be a $f(n)$-Almost Convex Point Set. Then, then there is an
algorithm $\mathcal{A}$ for such that, $\mathcal{A}$ runs in
$2^{\mathcal{O}{(n+f(n)\log n)}}$ time. In particular,

  1. 1.

When $f(n)=\mathcal{O}(n)$, $\mathcal{A}$ runs in $2^{\mathcal{O}(n\log n)}$
time.

  2. 2.

When $f(n)=\Omega(\frac{n}{\log n})$ and $f(n)=o(n)$, $\mathcal{A}$ runs in
$2^{o(n\log n)}$.

  3. 3.

When $f(n)=\mathcal{O}(\frac{n}{\log n})$, $\mathcal{A}$ runs in
$2^{\mathcal{O}(n)}$ time.

Therefore, for $f(n)=o(n)$, our algorithm for does better on $f(n)$-Almost
Convex Points Sets than the current best known algorithm [8].

##  5 Approximation Algorithms for

The problem is NP-hard as shown by Garey et al. in [6]. Garey et al. also
prove that there cannot be an FPTAS (fully polynomial time approximation
scheme) for this problem unless $P=NP$. At the same time, the case when all
the terminals lie on the boundary of a convex region admits an FPTAS as given
in [14]. We aim to conduct a more fine-grained analysis for the problem by
considering $f(n)$-Almost Convex Point Sets of $n$ terminals and studying the
existence of FPTASes for different functions $f(n)$. First, we present an
FPTAS for on $f(n)$-Almost Convex Sets of $n$ terminals, when
$f(n)=\mathcal{O}(\log n)$. Next, we prove that no FPTAS exists for the case
when $f(n)=\Omega(n^{\epsilon})$, where $\epsilon\in(0,1]$.

###  5.1 FPTAS for on Cases of Almost Convex Point Sets

We first propose an algorithm for computing the SMT of a planar graph $G$
having $N$ vertices and $n$ terminals, out of which $k$ terminals lie on the
outer face of $G$ and the remaining terminals lie within the boundary. Next,
following the procedure in [14] we get an FPTAS for on $f(n)$-Almost Convex
Sets of $n$ terminals, where $f(n)=\mathcal{O}(\log n)$.

We state the following proposition from Theorem 1 in [14]:

######  Proposition 5.1.

Let $\mathcal{P}$ be the vertices of any polygon in the plane, $\mathcal{K}$ a
subset of $\mathcal{P}$, and $\mathcal{T}$ a tree consisting of all the
vertices of $\mathcal{K}$ (and possibly some other vertices as well) and
contained entirely inside $\mathcal{P}$. Then on removing any edge of the
tree, we get two disjoint trees $\mathcal{T}_{1},\mathcal{T}_{2}$, such that
the vertices of $\mathcal{K}$ in each tree $\mathcal{T}_{i},i\in\\{1,2\\}$
form an interval in $\mathcal{K}$.

Using Proposition 5.1 and the Dreyfus-Wagner algorithm [4], we give an
algorithm for obtaining the SMT of a planar graph $G$.

Let $\mathcal{K}$ represent the set of terminals lying on the outer face of
$G$ and $\mathcal{R}$ be the set of terminals lying inside the outer face of
$G$. We have $|V(G)|=N$, $|\mathcal{K}\cup\mathcal{R}|=n$, and
$|\mathcal{K}|=k$. Let $C(\mathcal{L})$ denote the SMT in $G$ for a terminal
subset $\mathcal{L}\subseteq V(G)$. Let $B(v,\mathcal{L},[a,b))$ denote the
SMT in $G$ for the terminal set $\\{v\\}\cup\mathcal{L}\cup[a,b)$, where
$\mathcal{L}\subseteq\mathcal{R}$, $[a,b)$ is the set of vertices in
$\mathcal{K}$ forming an interval from vertex $a$ to $b$ in counterclockwise
direction along the outer boundary of $G$ including $a$ but excluding $b$,
$v\in V(G)\setminus(\mathcal{L}\cup[a,b))$, and the degree of $v$ is at least
$2$ in $B(v,\mathcal{L},[a,b))$. Let $A(v,\mathcal{L},[a,b))$ denote the SMT
in $G$ for the terminal set $\\{v\\}\cup\mathcal{L}\cup[a,b)$, where
$\mathcal{L}$, $[a,b)$, and $v$ are as defined in the previous case, and the
degree of $v$ is at most $1$ in $A(v,\mathcal{L},[a,b))$.

Splitting the SMT at a vertex $v$ of degree at least $2$ gives rise to two
smaller instances of the Steiner Minimal Tree problem on graphs.

$B(v,\mathcal{L},[a,b))=\min_{\Pi_{1},\Pi_{2},\Pi_{3}}\\{C(\\{v\\}\cup\mathcal{L}^{\prime}\cup[a,x))+C(\\{v\\}\cup(\mathcal{L}\setminus\mathcal{L}^{\prime})\cup[x,b))\\}$
(1)

where the conditions on $\mathcal{L}^{\prime}$ and $x$ are
$\Pi_{1}:\mathcal{L}^{\prime}\subseteq\mathcal{L}$,
$\Pi_{2}:x\in\mathcal{K},a<x<b$, and
$\Pi_{3}:\emptyset\subset\mathcal{L}^{\prime}\cup[a,x)\subset\mathcal{L}\cup[a,b)$.

The intuition is to root the tree at an internal terminal vertex and start
growing the Steiner tree from there. Observe that on removing one of the
internal vertices $v$ in the tree $\mathcal{T}$, we get one, two or three
disjoint subtrees. They induce a partition over the terminals. The terminals
in $\mathcal{K}$ in each of the subtrees form intervals in $\mathcal{K}$,
according to Proposition 5.1. Moreover, the terminals in $\mathcal{R}$ can be
partitioned in any way, not necessarily maintaining the interval structure.
This is captured in the following recurrence relation:

$C(\\{v\\}\cup\mathcal{L}\cup[a,b))=\min_{\Pi_{1},\Pi_{2},\Pi_{3}}\\{A(v,\mathcal{L}_{1},[a,c))+A(v,\mathcal{L}_{2},[c,d))+A(v,\mathcal{L}_{3},[d,b))\\}$
(2)

where the conditions on $\mathcal{L}_{1}$, $\mathcal{L}_{2}$,
$\mathcal{L}_{3}$, $c$, and $d$ are
$\Pi_{1}:\mathcal{L}_{1},\mathcal{L}_{2},\mathcal{L}_{3}\subseteq\mathcal{L}$,
$\Pi_{2}:\mathcal{L}_{1}\cup\mathcal{L}_{2}\cup\mathcal{L}_{3}=\mathcal{L}$,
and $\Pi_{3}:c,d\in\mathcal{K},a\leq c\leq d\leq b$ and we have

$A(v,\mathcal{L}^{\prime},[p,q))=\min\\{\min_{u\notin\mathcal{L}^{\prime}}\\{B(u,\mathcal{L}^{\prime},[p,q))+d(u,v)\\},\min_{u\in\mathcal{L}^{\prime}\cup[p,q)}\\{C(\mathcal{L}^{\prime}\cup[p,q))+d(u,v)\\}\\}$
(3)

Our aim is to compute
$C(\\{v\\}\cup(\mathcal{R}\setminus\\{v\\})\cup\mathcal{K})$, where
$v\in\mathcal{R}$. We precompute the shortest distance between all pairs of
vertices. We then compute the values of $C(.)$ and $B(.)$ in increasing order
of cardinality of subsets of vertices in $\mathcal{K}$ and $\mathcal{R}$. Let
$d(u,v)$ denote the shortest path length between $u$ and $v$. The base cases
are $C(\\{v\\}\cup\\{a\\})=d(v,a)$ for all $v\in V(G)$ and
$a\in\mathcal{K}\cup\mathcal{R}$.

Algorithm 2 Computation of SMT of planar graph $G$ with terminal set
$\mathcal{K}\cup\mathcal{R}$ Input: $G$, $\mathcal{K}$, $\mathcal{R}$

1:Compute the shortest distance between all pairs of vertices

2:for all $u\in V(G)$ and $a\in K\cup R$ do

3: Set $C(\\{u\\}\cup\\{a\\})=d(u,a)$

4:end for

5:Select a vertex $v\in\mathcal{R}$

6:for $i=1,\ldots,n-k-1$ do

7: for each $\mathcal{L}\subseteq\mathcal{R}\setminus\\{v\\}$ of size $i$ do

8: for $j=1,\ldots,k$ do

9: if j=k then

10: Compute $B(v,\mathcal{L},\mathcal{K})$ using Equation 1

11: Compute $C(\\{v\\}\cup\mathcal{L}\cup\mathcal{K})$ using Equation 2

12: else

13: for each $[a,b)\subseteq\mathcal{K}$ of size $j$ do

14: Compute $B(v,\mathcal{L},[a,b))$ using Equation 1

15: Compute $C(\\{v\\}\cup\mathcal{L}\cup[a,b))$ using Equation 2

16: end for

17: end if

18: end for

19: end for

20:end for

21:return $C(\\{v\\}\cup(\mathcal{R}\setminus\\{v\\})\cup\mathcal{K})$

We analyse the correctness and running time of Algorithm 2.

######  Theorem 5.2.

Consider a planar graph $G$ on $N$ vertices and a set
$\mathcal{K}\uplus\mathcal{R}\subseteq V(G)$ of $n$ terminals such that
$\mathcal{K}$ is defined as the terminals lying on the outer face of $G$.
Moreover, let $|\mathcal{K}|=k$. Then Algorithm 2 computes the SMT for
$\mathcal{K}\uplus\mathcal{R}$ in $G$ in time
$\mathcal{O}(N^{2}k^{4}4^{n-k}+Nk^{3}3^{n-k}+N^{3})$.

######  Proof 5.3.

Correctness of Algorithm 2. In order to prove the correctness of Algorithm 2,
we need to show that the Equations 1 and 2 are valid.

In Equation 1, $B(v,\mathcal{L},[a,b))$ denotes an SMT for the terminal set
$\\{v\\}\cup\mathcal{L}\cup[a,b)$, conditioned on the fact that the degree of
$v$ is at least $2$ in it. Let us split the SMT at vertex $v$ into two smaller
subtrees. This must also split the terminals in $[a,b)$ in two intervals
$[a,x)$ and $[x,b)$, respectively. Otherwise it would mean that the SMT has
crossing edges, which is not possible. The vertices in $\mathcal{L}$ can be
present in any of the two subtrees, hence we consider all possible partitions
of $\mathcal{L}$ into two subsets $\mathcal{L}^{\prime}$ and
$\mathcal{L}\setminus\mathcal{L}^{\prime}$. Thus for Equation 1,
$\mbox{LHS}\geq\mbox{RHS}$. On the other hand, the expression in the RHS of
Equation 1 is a tree containing the vertex subset
$\\{v\\}\cup\mathcal{L}\cup[a,b)$. Since, $B(v,\mathcal{L},[a,b))$ is an SMT
for the same vertex subset, in Equation 1 $\mbox{LHS}\geq\mbox{RHS}$.
Therefore, Equation 1 is valid.

For Equation 2, we take $v$ as the root of the SMT
$C(\\{v\\}\cup\mathcal{L}\cup[a,b))$. The degree of $v$ in the SMT can be $1$,
$2$, or $3$. Accordingly, on removing $v$, we will get $1$, $2$, or $3$
subtrees, with the condition that in each subtree the degree of $v$ is $1$.
Again, the terminals in $[a,b)$ are divided into smaller intervals $[a,c)$,
$[c,d)$ and $[d,b)$ for some $c,d\in\mathcal{K}$ satisfying $a<c<d<b$. The
terminals in $\mathcal{L}$ are divided among the subtrees in any combination.
The number of such intervals and partitions is equal to the degree of $v$ in
$C(\\{v\\}\cup\mathcal{L}\cup[a,b))$. The term
$A(v,\mathcal{L}^{\prime},[p,q))$ is obtained by minimizing across all SMTs
satisfying the condition that degree of $v$ in the SMT is $1$. Thus in
Equation 2, $\mbox{LHS}\geq\mbox{RHS}$. On the other hand, the RHS of Equation
2 given a tree containing vertices $\\{v\\}\cup\mathcal{L}\cup[a,b)$. Since
$C(\\{v\\}\cup\mathcal{L}\cup[a,b))$ is an SMT on the terminal set
$\\{v\\}\cup\mathcal{L}\cup[a,b)$, in Equation 2 $\mbox{LHS}\leq\mbox{RHS}$.
Thus, Equation 2 is valid.

Running time of Algorithm 2. All pairs shortest paths can be calculated in
$\mathcal{O}(N^{3})$ time. The time complexity of the dynamic program has two
components to it. One is due to computation of the B(.) values using Equation
1 and the other is for calculating the C(.) values using Equation 2.

  1. 1.

The number of computational steps for calculating $B(v,\mathcal{L},[a,b))$
using Equation 1 is of the order of the number of choices of $v$,
$\mathcal{L}$, $\mathcal{L}^{\prime}$, $[a,b)$, and $[a,x)$ such that
$\mathcal{L}\subset\mathcal{R}$, $\mathcal{L}^{\prime}\subseteq\mathcal{L}$,
$a,x,b\in\mathcal{K}$, $a\leq x\leq b$, and $v\in V(G)\setminus(L\cup[a,b))$.
Each vertex in $\mathcal{R}$ belongs to exactly one of the sets
$\mathcal{L}^{\prime}$, $\mathcal{L}\setminus\mathcal{L}^{\prime}$, or
$V(G)\setminus\mathcal{L}$. The vertices in $\mathcal{K}$ are partitioned into
three intervals, $[a,x)$, $[x,b)$, and $[b,a)$. There are at most $N$
possibilities for $v$. This gives us a running time of
$\mathcal{O}(Nk^{3}3^{n-k})$.

  2. 2.

The number of computational steps for calculating
$C(\\{v\\}\cup\mathcal{L}\cup[a,b))$ using Equation 2 is $3N$ times the order
of the number of choices of $v$, $\mathcal{L}$, $\mathcal{L}_{1}$,
$\mathcal{L}_{2}$, $a$, $b$, $c$, and $d$ such that
$\mathcal{L}\subset\mathcal{R}$, $\mathcal{L}_{1}\subseteq\mathcal{L}$,
$\mathcal{L}_{2}\subseteq\mathcal{L}$, $\\{a,c,d,b\\}\subseteq\mathcal{K}$,
$a\leq c\leq d\leq b$, and $v\in V(G)\setminus(\mathcal{L}\cup[a,b))$. Each
vertex in $\mathcal{R}$ belongs to exactly one of the sets $\mathcal{L}_{1}$,
$\mathcal{L}_{2}$, $\mathcal{L}_{3}$ or $V(G)\setminus\mathcal{L}$. The
vertices in $\mathcal{K}$ are partitioned into at most four intervals,
$[a,c)$, $[c,d)$, $[d,b)$ and $[b,a)$. There are at most $N$ possibilities for
$v$. The $3N$ factor is because calculating each of the $C(.)$ values involves
minimization over at most $3N$ terms. This gives us a running time of
$\mathcal{O}(N^{2}k^{4}4^{n-k})$.

Thus, the time complexity of the algorithm is
$\mathcal{O}(N^{2}k^{4}4^{n-k}+Nk^{3}3^{n-k}+N^{3})$.

We obtain the following corollary from the above theorem.

######  Corollary 5.4.

Consider a planar graph $G$ on $N$ vertices and a set
$\mathcal{K}\uplus\mathcal{R}\subseteq V(G)$ of $n$ terminals such that
$\mathcal{K}$ is defined by the terminals lying on the outer face of $G$.
Moreover, let $|\mathcal{K}|=k$ and let $|\mathcal{R}|=n-k=\mathcal{O}(\log
n)$. Then Algorithm 2 computes the SMT for $\mathcal{K}\uplus\mathcal{R}$ in
$G$ in time $N^{3}k^{4}n^{\mathcal{O}(1)}$.

Next we state the FPTAS for on $f(n)$-Almost Convex Sets of $n$ terminals.
This is achieved by converting the instance of into an instance of Steiner
Minimal Tree on graphs. The Steiner Minimal Tree problem shall be solved using
Algorithm 2. For this, we use the Algorithm 2 in [14]. We restate the
Algorithm 2 in [14] for our problem instance. We denote the set of terminals
with $\mathcal{P}$.

Algorithm 3 Computation of $(1+\epsilon)$-approximate SMT of $\mathcal{P}$
Input: $\mathcal{P},\epsilon$

1:Compute the convex hull of the set of terminals $\mathcal{P}$. Let the
region enclosed by the convex hull $\mathrm{CH}(\mathcal{P})$ be denoted by
$\mathbb{R}_{\mathrm{CH}(\mathcal{P})}$. Let the points in $\mathcal{P}$ lying
on $\mathrm{CH}(\mathcal{P})$ be $\mathcal{K}$ and
$\mathcal{R}=\mathcal{P}\setminus\mathcal{K}$.

2:We enclose the set of terminals $\mathcal{P}$ with the smallest axis-
parallel bounding square. Let its side length be $D$. We divide the bounding
square into same sized grids of side length $\frac{D\epsilon}{8n-12}$, where
$\epsilon$ is the approximation factor.

3:Let $\mathcal{V}_{0}$ be the set of all lattice points introduced in the
previous step, and $\mathcal{V}_{1}$ be the set of all lattice points lying on
the edges of $\mathrm{CH}(\mathcal{P})$. We define the weighted graph
$G_{f,\epsilon}$ to be the complete graph with vertex set
$V(G_{f,\epsilon})=\mathcal{K}\cup\mathcal{R}\cup(\mathcal{V}_{0}\cap\mathbb{R}_{\mathrm{CH}(\mathcal{P})})\cup\mathcal{V}_{1}$.
The edge weights are equal to the Euclidean distance between the two end
points.

4:Return the SMT $\mathcal{T}$ for the graph $G_{f,\epsilon}$ with
$\mathcal{K}\cup\mathcal{R}$ as the terminal set using Algorithm 2.

We analyse the correctness and running time of Algorithm 3.

######  Theorem 5.5.

Consider a set $\mathcal{P}$ of $n$ points such that $\mathcal{K}$ is defined
as the points lying on the convex hull of $\mathcal{P}$, i.e.
$\mathrm{CH}(\mathcal{P})$, and $\mathcal{R}=\mathcal{P}\setminus\mathcal{K}$.
Moreover, let $|\mathcal{K}|=k$. Then Algorithm 3 computes a
$(1+\epsilon)$-approximate SMT for $\mathcal{P}$ in time
$\mathcal{O}(\frac{n^{4}k^{4}}{\epsilon^{4}}4^{n-k})$.

######  Proof 5.6.

Correctness of Algorithm 3. In order to prove the correctness of Algorithm 3,
we need to show that $\mathcal{T}$ is a $(1+\epsilon)$-approximation of the
SMT of the terminal set $\mathcal{P}$, and $\mathcal{T}$ is indeed the SMT for
$\mathcal{K}\cup\mathcal{R}$ in the complete weighted graph $G_{f,\epsilon}$.

In [14], the concept of weight planar graphs is used. A graph $G$ is called
weight planar if it is a non-planar graph embedded on the Euclidean plane,
having non-negative edge weights, such that every pair of edges $(u,v)$ and
$(u^{\prime},v^{\prime})$ which intersect in this embedding of $G$, satisfy
the inequality:
$w(u,v)+w(u^{\prime},v^{\prime})>d(u,u^{\prime})+d(v,v^{\prime})$, where
$w(u,v)$ is the weight of the edge between vertices $u$ and $v$ and $d(x,y)$
is the length of the shortest path between vertices $x$ and $y$. Since the
edge weights of $G_{f,\epsilon}$ are the Euclidean distances between the
points, $G_{f,\epsilon}$ is a weight planar graph.

From Theorem 5 of [14], we get that the SMT of a weight planar graph does not
contain any crossing edges even though the input graph is non-planar. Because
the SMT does not contain any crossing edges and lies completely inside the
convex hull of the terminal pointset, the terminals on the outer boundary of
$G_{f,\epsilon}$, i.e. $\mathcal{K}$, follow the interval pattern as stated in
Proposition 5.1. Therefore, Algorithm 2 designed for planar graphs can be
applied in the case of weight planar graphs as well. So, $\mathcal{T}$ is the
SMT for $\mathcal{K}\cup\mathcal{R}$ in the complete weighted graph
$G_{f,\epsilon}$.

Finally, from Theorem 12 in [14], we get that the length of the Steiner tree
obtained from Algorithm 3 is at most $(1+\epsilon)$ times the length of the
SMT $\mathcal{T}^{*}$ of $\mathcal{P}$, i.e.
$|\mathcal{T}|\leq(1+\epsilon)|\mathcal{T}^{*}|$. Thus, we are done.

Running time of Algorithm 3. Constructing the convex hull takes
$\mathcal{O}(n\log n)$ time. The number of lattice points contained in the
bounding box is
$\big{(}\frac{8n-12}{\epsilon}\big{)}^{2}=\mathcal{O}(\frac{n^{2}}{\epsilon^{2}})$.
Thus, the number of vertices in the resultant graph $G_{f,\epsilon}$ is
$N=\mathcal{O}(\frac{n^{2}}{\epsilon^{2}})+n=\mathcal{O}(\frac{n^{2}}{\epsilon^{2}})$.
The time complexity of Algorithm 2 is
$\mathcal{O}(N^{2}k^{4}4^{n-k}+Nk^{3}3^{n-k}+N^{3})=\mathcal{O}(\frac{n^{4}k^{4}}{\epsilon^{4}}4^{n-k})$.
This step dominates the running time resulting in the complexity of Algorithm
3 being $\mathcal{O}(\frac{n^{4}k^{4}}{\epsilon^{4}}4^{n-k})$.

######  Theorem 5.7.

There exists an FPTAS for on an $f(n)$-Almost Convex Set of $n$ terminals,
where $f(n)=\mathcal{O}(\log n)$.

######  Proof 5.8.

From Theorem 5.5, we get a $(1+\epsilon)$-approximate SMT for any
$(n-k)$-Almost Convex Set of $n$ terminals in time
$\mathcal{O}(\frac{n^{4}k^{4}}{\epsilon^{4}}4^{n-k})$. For
$n-k=\mathcal{O}(\log n)$, we get the running time of Algorithm 3 to be
$\mathcal{O}(\frac{n^{4}k^{4}}{\epsilon^{4}}n^{\mathcal{O}(1)})$. Thus,
Algorithm 3 is an FPTAS for the Euclidean Steiner Minimal Tree problem on an
$\mathcal{O}(\log n)$-Almost Convex Set of $n$ terminals.

###  5.2 Hardness of Approximation for on Cases of Almost Convex Sets

In this section, we consider the problem on $f(n)$-Almost Convex Sets of $n$
terminal points, where $f(n)=\Omega(n^{\epsilon})$ for some
$\epsilon\in(0,1]$. We show that this problem cannot have an FPTAS. The proof
strategy is similar to that in [6]. First, we give a reduction for the problem
Exact Cover by $3$-Sets (defined below) to our problem to show that our
problem is NP-hard. Next, we consider a discrete version of our problem and
reduce our problem to the discrete version. The discrete version is in NP.
Therefore, this chain of reductions imply that the discrete version of our
problem is Strongly NP-complete and therefore cannot have an FPTAS, following
from [6]. Similar to the arguments in [6], this also implies that our problem
cannot have an FPTAS.

Before we describe our reductions, we take a look at the NP-hardness reduction
of the problem from the Exact Cover by 3-Sets (X3C) problem in [6]. In the X3C
problem, we are given a universe of elements $U=\\{1,2,\ldots,3n\\}$ and a
family $\mathbb{F}$ of $3$-element subsets $F_{1},F_{2},\ldots,F_{t}$ of the
$3n$ elements. The objective is to decide if there exists a subcollection
$\mathbb{F}^{\prime}\subseteq\mathbb{F}$ such that: (i) the elements of
$\mathbb{F}^{\prime}$ are disjoint, and (ii)
$\bigcup_{F^{\prime}\in\mathbb{F}^{\prime}}F^{\prime}=U$. The X3C problem is
NP-complete [7].

In [6], various gadgets are constructed, i.e. particular arrangements of a set
of points. These are then arranged on the plane in a way corresponding to the
given X3C instance. Figure 11 shows the reduced ESMT instance obtained for
$U=\\{1,2,3,4,5,6\\}$ and
$\mathbb{F}=\\{\\{1,2,4\\},\\{2,3,6\\},\\{3,5,6\\}\\}$ (taken from [6]). The
squares, hexagons (crossovers), shaded circles (terminators) and lines (rows)
all represent specific arrangements of a subset of points. Let $X(\mathbb{F})$
denote the reduced instance. The number of points in $X(\mathbb{F})$ is
bounded by a polynomial in $n$ and $t$. Let this polynomial be
$\mathcal{O}(t^{\gamma})$, as we can assume $t\geq n$ since otherwise it
trivially becomes a NO instance. Here $\gamma$ is some constant.

(a) Figure 11: Reduced instance of ESMT from X3C (taken from [6])

We restate Theorem 1 in [6].

######  Proposition 5.9.

Let $\mathcal{S}^{*}$ denote an SMT of $X(\mathbb{F})$, the instance obtained
by reducing the X3C instance $(n,\mathbb{F})$, and $|\mathcal{S}^{*}|$ denote
its length. If $\mathbb{F}$ has an exact cover, then $|\mathcal{S}^{*}|\leq
f(n,t,\hat{C})$, otherwise $|\mathcal{S}^{*}|\geq
f(n,t,\hat{C})+\frac{1}{200nt}$, where $t=|\mathbb{F}|$, $\hat{C}$ is the
number of crossovers, i.e. hexagonal gadgets, and $f$ is a positive real-
valued function of $n,t,\hat{C}$.

We extend this construction to prove NP-hardness for instances of where the
terminal set $\mathcal{P}$ has $\Omega(n^{\epsilon})$ points inside
$\mathrm{CH}(\mathcal{P})$. Here, $\epsilon\in(0,1]$ and $n$ is the number of
terminals.

Let us call the _length_ of a gadget to be the maximum horizontal distance
between any two points in that gadget. Similarly, we define the _breadth_ of a
gadget to be the maximum vertical distance between any two points in that
gadget.

(a)

(b)

(c)

Figure 12: The Terminator gadget symbol and arrangement of points

The _terminator_ gadget used is shown in Figure 12. The straight lines
represent a row of at least $1000$ points separated at distances of $1/10$ or
$1/11$. The angles between them are as shown. The upward terminator has the
point $A$ above the other points in the terminator, whereas the downward
terminator has the point $A$ below the other points. Firstly, we adjust the
number of points in the long rows, such that the length and breadth of the
terminators is same as that of the hexagonal gadgets (crossovers). We can fix
this length and breadth to be some constants, such that the number of points
in each gadget is also bounded by some constant. In our construction, we
modify the terminators $\Omega_{0}$, $\Omega_{1}$, and $\Omega_{2}$ as shown
in Figure 11 enclosed in squares. $\Omega_{1}$ is the terminator corresponding
to the first occurrence of the element $3n\in U$ in some set in $\mathbb{F}$
and $\Omega_{2}$ is the terminator corresponding to the last occurrence of
$3n$ in some set in $\mathbb{F}$ (if there are more than one occurrences of
$3n$). If there are no occurrences of $3n$, then it is trivially a no-
instance. The modified gadgets are shown in Figure 14. All the other gadgets
remain unaltered.

Figure 13: Conic Set: $\mathrm{Cone}(T,r,n)$

We call a set of points arranged as shown in Figure 13, as a Conic Set.

######  Definition 5.10.

A Conic Set is a set of points consisting of a point $T$, called the tip of
the cone, and the remaining points denoted by $\mathcal{S}$. Let $\mathcal{C}$
be the circle with $T$ as centre and radius $r$. All the points in
$\mathcal{S}$ lie on $\mathcal{C}$, such that the angle at the tip formed by
the two extreme points $L,R\in\mathcal{S}$, i.e. $\angle{LTR}=30^{\circ}$ in
the anticlockwise direction. So, we have $\overline{TL}=\overline{TR}=r$. The
distance between any two consecutive points in $\mathcal{S}$ is the same, say
$d$. Let the number of points in $\mathcal{S}$ be $n$. We denote the Conic Set
as $\mathrm{Cone}(T,r,n)$ and $\mathcal{S}$ as $\mathrm{Circ}(T,r,n)$. We call
$TL$ as the left slope of the Conic Set and $TR$ as the right slope of the
Conic Set.

(a)

(b)

(c)

Figure 14: The modified terminator gadgets

We use the Conic Set in the reduction for our problem. Now, we state the
reduction of an X3C instance $(n,\mathbb{F})$ to an instance
$X^{\prime}(\mathbb{F},\epsilon)$ of . Later, we show that the instance will
satisfy the desired properties on the number of terminals inside the convex
hull of the terminal set.

Algorithm $\mathcal{A}$ for construction of an ESMT instance
$X^{\prime}(\mathbb{F},\epsilon)$ from an X3C instance $(n,\mathbb{F})$:

  * •

Reduce the input X3C instance to the points configuration $X(\mathbb{F})$
according to the reduction given in [6].

  * •

Modify the terminators $\Omega_{0}$, $\Omega_{1}$, and $\Omega_{2}$ to as
shown in Figure 14 and call them $\Omega^{\prime}_{0}$, $\Omega^{\prime}_{1}$,
and $\Omega^{\prime}_{2}$. Let $DQCP$ be the smallest axis-parallel rectangle
bounding $X(\mathbb{F})$ after modifying the terminators, where $D$ is the
bottom leftmost point of $\Omega^{\prime}_{0}$.

  * •

Take $\alpha=\frac{1}{\epsilon}$. Define
$r=ct^{\alpha}=\mathcal{O}(t^{\alpha})$ and
$n^{\prime}=c^{\prime}t^{\gamma\alpha}=\mathcal{O}(t^{\gamma\alpha})$, where
$t=|\mathbb{F}|$ and $c$ and $c^{\prime}$ are constants. Add the
$\mathrm{Cone}(D,r,n^{\prime})$, such that $D$ is the tip of the Conic Set,
and the left slope $DE$ makes an angle of $120^{\circ}$ with $DP$. The right
slope $DF$ also makes an angle of $120^{\circ}$ with $DQ$.

Figure 15: The reduced instance $X^{\prime}(\mathbb{F},\epsilon)$

Now we prove a few properties of the constructed instance
$X^{\prime}(\mathbb{F},\epsilon)$.

######  Lemma 5.11.

All the points in $\mathrm{Circ}(D,r,n^{\prime})$ (according to Definition
5.10) lie on the convex hull of the reduced ESMT instance
$X^{\prime}(\mathbb{F},\epsilon)$ constructed by Algorithm $\mathcal{A}$,
where $\epsilon\in(0,1]$.

######  Proof 5.12.

By the construction of $\mathrm{Cone}(D,r,n^{\prime})$ in Algorithm
$\mathcal{A}$, let $\mathcal{C}$ be the circle on which all the points in
$\mathrm{Circ}(D,r,n^{\prime})$ lie. If we draw a tangent to $\mathcal{C}$ at
any of the points in $\mathrm{Circ}(D,r,n^{\prime})$, then all the remaining
points in the configuration $X^{\prime}(\mathbb{F},\epsilon)$ lie towards one
side of the tangent. We know that if we can find a line passing through a
point such that all the other points in the plane lie on one side of the line,
then the point lies on the convex hull of the points in the plane. Therefore,
all the points in $\mathrm{Circ}(D,r,n^{\prime})$ lie on the convex hull of
the reduced instance $X^{\prime}(\mathbb{F},\epsilon)$.

Let us denote the convex hull of $X^{\prime}(\mathbb{F},\epsilon)$ by
$\mathrm{CH}(X^{\prime}(\mathbb{F},\epsilon))$ and that of the points lying
inside or on the bounding rectangle $\mathrm{PDQC}$, i.e.
$X^{\prime}(\mathbb{F},\epsilon)\setminus\mathrm{Circ}(D,r,n^{\prime})$ by
$\mathrm{CH}(X^{\prime}(\mathbb{F},\epsilon)\setminus\mathrm{Circ}(D,r,n^{\prime}))$.

######  Lemma 5.13.

The reduced ESMT instance $X^{\prime}(\mathbb{F},\epsilon)$ constructed by
Algorithm $\mathcal{A}$ has $\Omega(N^{\epsilon})$ points inside the convex
hull, where $\epsilon\in(0,1]$ and $N$ is the total number of terminals in
$X^{\prime}(\mathbb{F},\epsilon)$.

######  Proof 5.14.

$\mathrm{CH}(X^{\prime}(\mathbb{F},\epsilon))$ contains all the points in
$\mathrm{Circ}(D,r,n^{\prime})$ by Lemma 5.11. $\mathrm{Circ}(D,r,n^{\prime})$
contains $n^{\prime}=\mathcal{O}(t^{\gamma\alpha})$ points.

Now we need to analyze the number of points on
$\mathrm{CH}(X^{\prime}(\mathbb{F},\epsilon)\setminus\mathrm{Circ}(D,r,n^{\prime}))$.
The remaining points in $X(\mathbb{F})$, i.e.
$X(\mathbb{F})\setminus\mathrm{CH}(X^{\prime}(\mathbb{F},\epsilon)\setminus\mathrm{Circ}(D,r,n^{\prime}))$
must lie within the convex hull of the entire construction, i.e.
$X^{\prime}(\mathbb{F},\epsilon)$. From the construction in Algorithm
$\mathcal{A}$, no point on the connecting rows can be a part of
$\mathrm{CH}(X^{\prime}(\mathbb{F},\epsilon)\setminus\mathrm{Circ}(D,r,n^{\prime}))$
as there is no line passing through it, which contains all terminals on one
side of it. The same thing holds for the square and hexagonal gadgets as well,
except the hexagonal gadgets corresponding to the last element of the last set
in the family, i.e. $F_{t}$. Thus, only the terminators and the hexagonal
gadgets corresponding to the last element of $F_{t}$ contribute points to
$\mathrm{CH}(X^{\prime}(\mathbb{F},\epsilon)\setminus\mathrm{Circ}(D,r,n^{\prime}))$.

If we look at the arrangement of points in the terminators (modified as well
as those left unchanged) and the hexagonal gadgets as shown in Figures 12 and
16, the convex hull of each of these gadgets consists of constantly many
points. Therefore, the number of points each of these gadgets contribute to
$\mathrm{CH}(X^{\prime}(\mathbb{F},\epsilon)\setminus\mathrm{Circ}(D,r,n^{\prime}))$
is bounded by some constant. The number of terminators is $6t+2$ and the
number of hexagonal gadgets corresponding to the last element of $F_{t}$ is at
most $3n$. Therefore, the number of points on
$\mathrm{CH}(X^{\prime}(\mathbb{F},\epsilon)\setminus\mathrm{Circ}(D,r,n^{\prime}))$
is $\mathcal{O}(t+n)=\mathcal{O}(t)$ as $n\leq t$.

The instance $X(\mathbb{F})$ obtained via reduction from X3C has $6t+2$
terminators, $t$ squares, at most $9nt$ crossovers (hexagonal gadgets), and
$\mathcal{O}(nt)$ connecting rows of points. The number of gadgets is
$\mathcal{O}(nt)$. Therefore, the total number of points in $X(\mathbb{F})$ is
$\Omega(nt)=\omega(t)$. The modified terminators result in a constantly many
increase in the number of points. So, we have $\gamma>1$.

Thus, the number of points inside the convex hull is $\Omega(t^{\gamma})$ and
those on the convex hull is $\mathcal{O}(t^{\gamma\alpha})$. So, the total
number of terminals is
$N=\mathcal{O}(t^{\gamma\alpha})+\mathcal{O}(t^{\gamma})=\mathcal{O}(t^{\gamma\alpha})$,
and those inside the convex hull is
$\Omega(t^{\gamma})=\Omega(N^{1/\alpha})=\Omega(N^{\epsilon})$ as
$\alpha=\frac{1}{\epsilon}$.

Figure 16: The hexagonal gadget (crossover), the convex hull of the gadget is
the quadrilateral $\rm abcd$ (taken from [6])

We further prove structural properties of SMTs of the reduced instance
$X^{\prime}(\mathbb{F},\epsilon)$ when considering the modified gadgets
$\Omega^{\prime}_{0}$, $\Omega^{\prime}_{1}$, and $\Omega^{\prime}_{2}$.

######  Lemma 5.15.

Consider an SMT $\mathcal{S}^{*}$ of the ESMT instance $X(\mathbb{F})$
obtained via reduction from the X3C instance $(n,\mathbb{F})$ as per [6].
Consider a tree $\mathcal{S^{\prime}}^{*}$ on the terminal set of
$X^{\prime}(\mathbb{F},\epsilon)$ obtained from $\mathcal{S}^{*}$ as follows:
Consider the modified terminator gadgets
$\Omega^{\prime}_{i},\leavevmode\nobreak\ i\in\\{0,1,2\\}$ as in Algorithm
$\mathcal{A}$. For each $i\in\\{0,1,2\\}$, the edge $B_{i}O_{i}$ is excluded
from $\mathcal{S}^{*}$ and the edge $D_{i}O_{i}$ is included to form
$\mathcal{S^{\prime}}^{*}$. $\mathcal{S^{\prime}}^{*}$ is an SMT for the
terminal set of $X^{\prime}(\mathbb{F},\epsilon)$.

######  Proof 5.16.

Consider $\mathcal{S}^{*}$. Due to Lemma 4 of [6], Steiner points of
$\mathcal{S}^{*}$ can only be connected to points in the triangular and square
gadgets. Lemma 5 of [6] states that if there are two terminals $x,y\in
X(\mathbb{F})$ and the distance between $x$ and $y$ does not exceed
$\frac{1}{10}$, then $(x,y)$ is an edge of $\mathcal{S}^{*}$. So in
$\mathcal{S}^{*}$, for each $i\in\\{0,1,2\\}$ all the points on $B_{i}O_{i}$
are joined together along $B_{i}O_{i}$. Lemma 5 of [6] also holds true on
modifying the terminators to $\Omega^{\prime}_{i},\leavevmode\nobreak\
i\in\\{0,1,2\\}$. Now, we join all the points on $D_{i}O_{i}$ along
$D_{i}O_{i}$. This gives us the SMT $\mathcal{S^{\prime}}^{*}$ for the
terminal set of $X^{\prime}(\mathbb{F},\epsilon)$.

Now we focus on the structure of the SMT of
$X^{\prime}(\mathcal{F},\epsilon)$. The SMT is basically the union of the SMT
$\mathcal{S^{\prime}}^{*}$ of the points in the bounding rectangle $PDQC$ as
stated in Lemma 5.15 and the SMT of the set of points
$\mathrm{Cone}(D,r,n^{\prime})$.

$\mathrm{CH}(X^{\prime}(\mathbb{F},\epsilon)\setminus\mathrm{Circ}(D,r,n^{\prime}))$
is enclosed by the bounding rectangle $PDQC$ and $D$ must lie on
$\mathrm{CH}(X^{\prime}(\mathbb{F},\epsilon)\setminus\mathrm{Circ}(D,r,n^{\prime}))$.
We label the vertices of
$\mathrm{CH}(X^{\prime}(\mathbb{F},\epsilon)\setminus\mathrm{Circ}(D,r,n^{\prime}))$
as $D,P_{1},P_{2},\ldots,P_{k}$ in the counter-clockwise order. Let
$\mathrm{CH}(X^{\prime}(\mathbb{F},\epsilon))$ be the convex hull of all the
points. By Lemma 5.11, all the points in $\mathrm{Circ}(D,r,n^{\prime})$ lie
on $\mathrm{CH}(X^{\prime}(\mathbb{F},\epsilon))$. Let $EP_{i}$ and $FP_{j}$
be edges in $\mathrm{CH}(X^{\prime}(\mathbb{F},\epsilon))$, such that
$P_{i},P_{j}\notin\mathrm{Circ}(D,r,n^{\prime})$.

The SMT of $X^{\prime}(\mathbb{F},\epsilon)$ clearly lies inside its convex
hull, $\mathrm{CH}(X^{\prime}(\mathbb{F},\epsilon))$. We show that the Steiner
hull can be further restricted to the bounding rectangle $PDQC$ and the convex
polygon formed by the points in $\mathrm{Cone}(D,r,n^{\prime})$. For this we
use Theorem 1.5 in [9], as stated below.

######  Proposition 5.17.

[9] Let $H$ be a Steiner hull of $N$. By sequentially removing wedges $\rm
abc$ from the remaining region, where $\rm a$, $\rm b$, $\rm c$ are terminals
but $\triangle{\rm abc}$ contains no other terminal, $a$ and $c$ are on the
boundary and $\angle{\rm abc}\geq 120^{\circ}$, a Steiner hull $H^{\prime}$
invariant to the sequence of removal is obtained.

######  Lemma 5.18.

The region comprising of the bounding rectangle $PDQC$ according to Algorithm
$\mathcal{A}$ and the convex polygon formed by the set of points
$\mathrm{Cone}(D,r,n^{\prime})$ is a Steiner hull of
$X^{\prime}(\mathbb{F},\epsilon)$.

######  Proof 5.19.

Firstly, let us consider the wedge $EP_{i+1}P_{i}$. All the points are
terminals, $E$ and $P_{i}$ are boundary points, and $\triangle{EP_{i+1}P_{i}}$
contains no other terminal. Now, $\angle{EP_{i+1}P_{i}}$ is greater than the
exterior angle of $\angle{EP_{i+1}D}$, which in turn is greater than
$\angle{EDP_{i+1}}$. $\angle{EDP_{i+1}}\geq\angle{\rm EDP}=120^{\circ}$, by
the construction. Therefore, $\angle{EP_{i+1}P_{i}}\geq 120^{\circ}$. By
applying Proposition 5.17, we can remove the wedge $EP_{i+1}P_{i}$ from the
convex hull $\mathrm{CH}(X^{\prime}(\mathbb{F},\epsilon))$ to get a smaller
Steiner hull. This can be repeated for the wedges
$EP_{i+2}P_{i+1},EP_{i+3}P_{i+2},\ldots,EDP_{k}$. The same argument can also
be used to get rid of the wedges
$FP_{j-1}P_{j},FP_{j-2}P_{j-1},\ldots,FDP_{1}$. So, we get the final Steiner
hull $H^{\prime}$ to be the union of the bounding rectangle $PDQC$ and the
convex polygon formed by the points in $\mathrm{Cone}(D,r,n^{\prime})$.

Given the nature of the above Steiner hull, we show that we can treat
$X(\mathbb{F})$ and $\mathrm{Cone}(D,r,n^{\prime})$ separately.

######  Lemma 5.20.

There is an SMT of $X^{\prime}(\mathbb{F},\epsilon)$ that is the union of an
SMT of $X(\mathbb{F})$ and an SMT of the points in
$\mathrm{Cone}(D,r,n^{\prime})$, with $D$ being common to both of them.

######  Proof 5.21.

According to Lemma 5.18, there is an SMT of $X^{\prime}(\mathbb{F},\epsilon)$
that lies completely inside the the bounding quadrilateral $PDQC$ and the
convex polygon formed by $\mathrm{Cone}(D,r,n^{\prime})$. These two regions
have $D$ as the only common point. Therefore, $D$ is an articulation point in
the tree and connects these two regions. So, we have this SMT of
$X^{\prime}(\mathbb{F},\epsilon)$ as the union of an SMT of $X(\mathbb{F})$
and an SMT of the points in $\mathrm{Cone}(D,r,n^{\prime})$.

We can identify a structure for an SMT of the points in
$\mathrm{Cone}(D,r,n^{\prime})$ using [16].

######  Lemma 5.22.

There is an SMT of the points in $\mathrm{Cone}(D,r,n^{\prime})$ that is as
shown in Figure 17. In the SMT, $D$ is connected to the two middle points in
$\mathrm{Circ}(D,r,n^{\prime})$ via a Steiner point $S^{t}$. The other points
in $\mathrm{Circ}(D,r,n^{\prime})$ are connected along the circumference.

######  Proof 5.23.

The number of points in $\mathrm{Circ}(D,r,n^{\prime})$ is
$\mathcal{O}(t^{\gamma\alpha})$. We can take the constant factor to be large
enough so that $|\mathrm{Circ}(D,r,n^{\prime})|>=12$. If we complete the
regular polygon on $\mathcal{C}$ having $\mathrm{Circ}(D,r,n^{\prime})$ as a
subset of its vertices, then it contains more than $12$ vertices and along
with the centre $D$ has a SMT with structure given in [16].

Let the Steiner tree for $\mathrm{Cone}(D,r,n^{\prime})$ as shown in Figure 17
be denoted by $\mathcal{T}_{1}$. If this is not minimal, then there exists
another Steiner tree $\mathcal{T}_{2}$ such that
$|\mathcal{T}_{2}|<|\mathcal{T}_{1}|$. Then we can replace $\mathcal{T}_{1}$
by $\mathcal{T}_{2}$ in the SMT of the regular polygon and its centre to get a
shorter Steiner tree. This contradicts the minimality of the structure given
in [16]. Therefore, the SMT of $\mathrm{Cone}(D,r,n^{\prime})$ follows the
structure in Figure 17.

Figure 17: SMT of $\mathrm{Cone}(D,r,n^{\prime})$

Finally, we prove the NP-hardness of on $f(n)$-Almost Convex Sets of $n$
terminals, when $f(n)=\Omega(n^{\epsilon})$ for some $\epsilon\in(0,1]$.

######  Theorem 5.24.

Let $\mathcal{S}^{*}_{\mathbb{F},\epsilon}$ denote an SMT of
$X^{\prime}(\mathbb{F},\epsilon)$ and
$|\mathcal{S}^{*}_{\mathbb{F},\epsilon}|$ denote its length. If $\mathbb{F}$
has an exact cover, then $|\mathcal{S}^{*}_{\mathbb{F},\epsilon}|\leq
f(n,t,\hat{C})+|\mathcal{T}_{1}|$, otherwise
$|\mathcal{S}^{*}_{\mathbb{F},\epsilon}|\geq
f(n,t,\hat{C})+\frac{1}{200nt}+|\mathcal{T}_{1}|$, where $\hat{C}$ is the
number of crossovers, i.e. hexagonal gadgets, and $f$ is a positive real-
valued function of $n,t,\hat{C}$ as stated in Proposition 5.9.

######  Proof 5.25.

From Lemma 5.20, we have
$|\mathcal{S}^{*}_{\mathbb{F},\epsilon}|=|\mathcal{S}^{*}|+|\mathcal{T}_{1}|$.
From Lemma 5.22, we can compute the length of $\mathcal{T}_{1}$ as a function
of $t$, $\alpha$, and $\gamma$. Finally, using Proposition 5.9 we get the
required reduction.

Since it is not known if the ESMT problem is in NP, Garey et al. [6] show the
NP-completeness of a related problem called the Discrete Euclidean Steiner
Minimal Tree (DESMT) problem, which is in NP. We define the DESMT problem as
given in [6]. The DESMT problem takes as input a set $\mathcal{X}$ of integer-
coordinate points in the plane and a positive integer $L$, and asks if there
exists a set $\mathcal{Y}\supseteq\mathcal{X}$ of integer-coordinate points
such that some spanning tree $\mathcal{T}$ for $\mathcal{Y}$ satisfies
$|\mathcal{T}|_{d}\leq L$, where $|\mathcal{T}|_{d}=\Sigma_{e\in
E(\mathcal{T})}\lceil\overline{e}\rceil$, i.e. we round up the length of each
edge to the least integer not less than it.

In order to show that DESMT is NP-hard, the same reduction as that of the ESMT
problem can be used, followed by scaling and rounding the coordinates of the
points. Theorem 4 of [6] proves that the DESMT problem is NP-Complete.
Moreover, since it is Strongly NP-Complete, the DESMT problem does not admit
any FPTAS. Finally in Theorem 5 of [6], Garey et al. show that as a
consequence, the ESMT problem does not have any FPTAS as well.

Now we show that the DESMT problem is NP-hard even on $f(n)$-Almost Convex
Sets of $n$ terminals, when $f(n)=\Omega(n^{\epsilon})$ and where
$\epsilon\in(0,1]$.

In Section 7 of [6], the reduced instance $X(\mathbb{F})$ of ESMT is converted
into an instance $X_{d}(\mathbb{F})$ of DESMT. The conversion is as follows:
$X_{d}(\mathbb{F})=\\{(\lceil 12M\cdot 200nt\cdot x_{1}\rceil,\lceil 12M\cdot
200nt\cdot x_{2}\rceil):x=(x_{1},x_{2})\in X(\mathbb{F})\\}$, where
$M=|X(\mathbb{F})|$.

We apply a similar conversion to the reduced ESMT instance
$X^{\prime}(\mathbb{F},\epsilon)$, to convert it into a DESMT instance of an
$\Omega(n^{\epsilon})$-Almost Convex Set. The conversion goes as follows:
$X^{\prime}_{d}(\mathbb{F},\epsilon)=\\{(\lceil 12N\cdot 200nt\cdot
x_{1}\rceil,\lceil 12N\cdot 200nt\cdot x_{2}\rceil):x=(x_{1},x_{2})\in
X^{\prime}(\mathbb{F},\epsilon)\\}$, where
$N=|X^{\prime}(\mathbb{F},\epsilon)|$.

The next two lemmas establish the validity of
$X^{\prime}_{d}(\mathbb{F},\epsilon)$ as an instance of DESMT and the upper
bounds on the size of the constructed instance. Note that the reduction from
X3C followed by the conversion can be done in polynomial time.

######  Lemma 5.26.

The instance $X^{\prime}_{d}(\mathbb{F},\epsilon)$ constructed above is a
valid DESMT instance.

######  Proof 5.27.

All the points in $X^{\prime}_{d}(\mathbb{F},\epsilon)$ have integer
coordinates according to the conversion stated above. So, it is a DESMT
instance.

######  Lemma 5.28.

The reduced DESMT instance $X^{\prime}_{d}(\mathbb{F},\epsilon)$ has $N$
distinct points, where $N=|X^{\prime}(\mathbb{F},\epsilon)|$.

######  Proof 5.29.

The minimum distance between any two points in
$X^{\prime}(\mathbb{F},\epsilon)$ is that between two consecutive points of
$\mathrm{Circ}(D,r,n^{\prime})$, which is $\mathcal{O}(\frac{1}{t^{\gamma}})$.
Recall Lemma 5.13 which establishes that $N=\mathcal{O}(t^{\gamma\alpha})$.
So, the minimum distance between any two points in
$X^{\prime}_{d}(\mathbb{F},\epsilon)$ is $\mathcal{O}(N\cdot
nt\cdot\frac{1}{t^{\gamma}})=\mathcal{O}(nt^{\alpha+1})$. Because of the
substantial distance obtained between points after scaling, the rounding will
not cause any distinct points of $X^{\prime}_{d}(\mathbb{F},\epsilon)$ to
coincide. Therefore, the number of points remains unchanged, i.e.
$|X^{\prime}_{d}(\mathbb{F},\epsilon)|=|X^{\prime}(\mathbb{F},\epsilon)|=N$.

Now we present the following lemma for the constructed DESMT instance
$X^{\prime}_{d}(\mathbb{F},\epsilon)$ analogous to Lemma 5.13 for the ESMT
instance $X^{\prime}(\mathbb{F},\epsilon)$.

######  Lemma 5.30.

The reduced DESMT instance $X^{\prime}_{d}(\mathbb{F},\epsilon)$ constructed
is an $\Omega(N^{\epsilon})$-Almost Convex Set, where
$N=|X^{\prime}_{d}(\mathbb{F},\epsilon)|$.

######  Proof 5.31.

From Lemma 5.13, we know that the reduced ESMT instance
$X^{\prime}(\mathbb{F},\epsilon)$ has $\Omega(N^{\epsilon})$ points inside its
convex hull $\mathrm{CH}(X^{\prime}(\mathbb{F},\epsilon))$, and
$N=|X^{\prime}(\mathbb{F},\epsilon)|$. The number of points after conversion
remains the same by Lemma 5.28. We need to show that after conversion, except
for the points of $\mathcal{O}(t)$ gadgets, no other points inside the convex
hull $\mathrm{CH}(X^{\prime}(\mathbb{F},\epsilon))$ lie on the new convex hull
$\mathrm{CH}(X^{\prime}_{d}(\mathbb{F},\epsilon))$. The number of points in
each of the $\mathcal{O}(t)$ anomalous gadgets are constant in number, and
hence not too many points from the interior of
$\mathrm{CH}(X^{\prime}(\mathbb{F},\epsilon))$ can lie on
$\mathrm{CH}(X^{\prime}_{d}(\mathbb{F},\epsilon))$.

After conversion, all the points on a horizontal connecting row have the same
$y$-coordinate, as they initially had the same $y$-coordinate and therefore
undergo the same transformation. Thus, all the points on a horizontal
connecting row still lie on a horizontal line segment in
$X^{\prime}_{d}(\mathbb{F},\epsilon)$. Similarly, all the points on a vertical
connecting row still lie on a vertical line segment in
$X^{\prime}_{d}(\mathbb{F},\epsilon)$. This implies that none of the points on
the connecting rows can be a part of
$\mathrm{CH}(X^{\prime}_{d}(\mathbb{F},\epsilon))$ as there can be no line
passing through them that also contains all terminal points on one side of it.

The same thing holds for the square and hexagonal gadgets (crossovers) as
well, except the hexagonal gadgets placed at the beginning or end of any row.
This is because all the points which are a part of these square and hexagon
gadgets are surrounded by connecting row points all four sides, above, below,
left and right. So again, only the terminators and the hexagonal gadgets
appearing at the beginning or end of any row contribute to
$\mathrm{CH}(X^{\prime}_{d}(\mathbb{F},\epsilon))$.

Now, since we had adjusted the number of points in the long rows of the
terminators and hexagonal gadgets such that their lengths and breadths are
some constants, the number of points in each of the terminators and hexagonal
gadgets can be bounded by some constant as the minimum distance between any
two consecutive points on the long rows or standard rows is at least
$\frac{1}{11}$. Therefore, each of these gadgets contribute some constantly
many points to $\mathrm{CH}(X^{\prime}_{d}(\mathbb{F},\epsilon))$.

As we have seen in Lemma 5.13, the number of terminators is $6t+2$ and the
number of hexagonal gadgets corresponding to the beginning or end of any row
is at most $6n$. Therefore, the number of points contributed by the
terminators and the hexagonal gadgets placed at the beginning or the end of
any row, to $\mathrm{CH}(X^{\prime}_{d}(\mathbb{F},\epsilon)$ is
$\mathcal{O}(t+n)=\mathcal{O}(t)$, as $n\leq t$. Even if all the points in
$\mathrm{Circ}(D,r,n^{\prime})$ lie on the new convex hull
$\mathrm{CH}(X^{\prime}_{d}(\mathbb{F},\epsilon)$, we have
$\Omega(t^{\gamma})=\Omega(N^{\epsilon})$ points inside it. Thus we are done.

We get the following theorem from Lemmas 5.26, 5.28 and 5.30.

######  Theorem 5.32.

The instance $X^{\prime}_{d}(\mathbb{F},\epsilon)$ constructed is a valid
DESMT instance on an $\Omega(N^{\epsilon})$-Almost Convex Set, where
$|X^{\prime}_{d}(\mathbb{F},\epsilon)|=|X^{\prime}(\mathbb{F},\epsilon)|=N$.

Following Theorems 3 and 4 in [6], we get that the DESMT problem is NP-
Complete for $\Omega(N^{\epsilon})$-Almost Convex Sets, where $N$ is the total
number of terminals. Since we get the reduced instance
$X^{\prime}_{d}(\mathbb{F},\epsilon)$ from the X3C instance $(n,\mathbb{F})$,
the DESMT problem is strongly NP-complete for $\Omega(N^{\epsilon})$-Almost
Convex Sets, and does not admit any FPTAS.

Using Theorem 5 of [6], we get that if the ESMT problem has an FPTAS, then the
X3C problem can be solved in polynomial time. The Theorem also applies for our
case of $\Omega(N^{\epsilon})$-Almost Convex Sets. Therefore, we get the
following theorem,

######  Theorem 5.33.

There does not exist any FPTAS for the ESMT problem on $f(n)$-Almost Convex
Sets of $n$ terminals, where $f(n)=\Omega(n^{\epsilon})$ and
$\epsilon\in(0,1]$, unless $\mbox{P}=\mbox{NP}$.

##  6 Conclusion

In this paper, we first study ESMT on vertices of $2$-CPR $n$-gons and design
a polynomial time algorithm. It remains open to design a polynomial time
algorithm for ESMT on $k$-CPR $n$-gons, or show NP-hardness for the problem.
Next, we study the problem on $f(n)$-Almost Convex Sets of $n$ terminals. For
this NP-hard problem, we obtain an algorithm that runs in
$2^{\mathcal{O}(f(n)\log n)}$ time. We also design an FPTAS when
$f(n)=\mathcal{O}(\log n)$. On the other hand, we show that there cannot be an
FPTAS if $f(n)=\Omega(n^{\epsilon})$ for any $\epsilon\in(0,1]$, unless
$\mbox{P}=\mbox{NP}$. The question of existence of FPTASes when $f(n)$ is a
polylogarithmic function remains open.

## References

  * [1] Sanjeev Arora.  Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems.  Journal of the ACM (JACM), 45(5):753–782, 1998.
  * [2] Marcus Brazil, Ronald L Graham, Doreen A Thomas, and Martin Zachariasen.  On the history of the Euclidean Steiner tree problem.  Archive for history of exact sciences, 68(3):327–354, 2014.
  * [3] EJ Cockayne.  On the Steiner problem.  Canadian Mathematical Bulletin, 10(3):431–450, 1967.
  * [4] Stuart E Dreyfus and Robert A Wagner.  The Steiner problem in graphs.  Networks, 1(3):195–207, 1971.
  * [5] Ding-Zhu Du, Frank K. Hwang, and JF Weng.  Steiner minimal trees for regular polygons.  Discrete & Computational Geometry, 2(1):65–84, 1987.
  * [6] Michael R Garey, Ronald L Graham, and David S Johnson.  The complexity of computing Steiner minimal trees.  SIAM Journal on Applied Mathematics, 32(4):835–859, 1977\.
  * [7] Michael R Garey and David S Johnson.  Computers and intractability, volume 174.  freeman San Francisco, 1979.
  * [8] FK Hwang.  A linear time algorithm for full Steiner trees.  Operations Research Letters, 4(5):235–237, 1986.
  * [9] FK Hwang, DS Richards, and P Winter.  The Steiner tree problem. Annals of Discrete Mathematics series, vol. 53, 1992.
  * [10] Sándor Kisfaludi-Bak, Jesper Nederlof, and Karol Węgrzycki.  A gap-ETH-tight approximation scheme for Euclidean TSP.  In 2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS), pages 351–362. IEEE, 2022.
  * [11] Zdzislaw Alexander Melzak.  On the problem of Steiner.  Canadian Mathematical Bulletin, 4(2):143–148, 1961.
  * [12] Satish B Rao and Warren D Smith.  Approximating geometrical graphs via “spanners” and “banyans”.  In Proceedings of the thirtieth annual ACM symposium on Theory of computing, pages 540–550, 1998.
  * [13] J Hyam Rubinstein, Doreen A Thomas, and Nicholas C Wormald.  Steiner trees for terminals constrained to curves.  SIAM Journal on Discrete Mathematics, 10(1):1–17, 1997.
  * [14] J Scott Provan.  Convexity and the Steiner tree problem.  Networks, 18(1):55–72, 1988.
  * [15] Michael Ian Shamos and Dan Hoey.  Closest-point problems.  16th Annual Symposium on Foundations of Computer Science (sfcs 1975), pages 151–162, 1975.
  * [16] Jia Feng Weng and Raymond Sydney Booth.  Steiner minimal trees on regular polygons with centre.  Discrete Mathematics, 141(1-3):259–274, 1995.