Department of Computer Science & Engineering, Indian Institute of Technology
Bombay, India. and https://sites.google.com/view/homepage-of-sujoy-
bhore/homesujoy.bhore@gmail.comhttps://orcid.org/0000-0003-0104-1659
Department of Information and Computing Sciences, Utrecht University,
Netherlands and https://www.uu.nl/staff/FMKlute
f.m.klute@uu.nlhttps://orcid.org/0000-0002-7791-3604 Supported by the
Netherlands Organisation for Scientific Research (NWO) under project no.
612.001.651 and the Austrian Science Foundation (FWF) grant J4510. Department
of Information and Computing Sciences, Utrecht University, Netherlands and
https://www.uu.nl/staff/MLoffler/Profile<EMAIL_ADDRESS>Algorithms and
Complexity Group, TU Wien, Austria and
https://www.ac.tuwien.ac.at/people/noellenburg/noellenburg@ac.tuwien.ac.athttps://orcid.org/0000-0003-0454-3937
Algorithms and Complexity Group, TU Wien, Austria and
https://www.ac.tuwien.ac.at/people/sterziadis/sterziadis@ac.tuwien.ac.athttps://orcid.org/0000-0001-5161-3841
Algorithms and Complexity Group, TU Wien, Austria and
https://www.ac.tuwien.ac.at/people/avilledieu/avilledieu@ac.tuwien.ac.athttps://orcid.org/0000-0001-6196-8347Supported
by the Austrian Science Fund (FWF) under grant P31119. Sujoy Bhore, Fabian
Klute, Maarten Löffler, Martin Nöllenburg, Soeren Terziadis and Anaïs
Villedieu [500]Theory of computation Computational geometry Sang Won Bae and
Heejin Park 2 33rd International Symposium on Algorithms and Computation
(ISAAC 2022) ISAAC 2022 ISAAC 2022 December 19–21, 2022 Seoul, Korea 248 60

###### Acknowledgements.

The authors would like to thank Thekla Hamm and Irene Parada for the valuable
discussion in particular concerning the results of Section 3.[#1][#1]

# Minimum Link Fencing

Sujoy Bhore  Fabian Klute  Maarten Löffler  Martin Nöllenburg  Soeren
Terziadis  Anaïs Villedieu

###### Abstract

We study a variant of the geometric multicut problem, where we are given a set
$\mathcal{P}$ of colored and pairwise interior-disjoint polygons in the plane.
The objective is to compute a set of simple closed polygon boundaries
(_fences_) that separate the polygons in such a way that any two polygons that
are enclosed by the same fence have the same color, and the total number of
links of all fences is minimized. We call this the _minimum link fencing_
(MLF) problem and consider the natural case of _bounded minimum link fencing_
(BMLF), where $\mathcal{P}$ contains a polygon $Q$ that is unbounded in all
directions and can be seen as an outer polygon. We show that BMLF is NP-hard
in general and that it is -time solvable when each fence contains at most two
polygons and the number of segments per fence is the parameter. Finally, we
present an $O(n\log n)$-time algorithm for the case that the convex hull of
$\mathcal{P}\setminus\\{Q\\}$ does not intersect $Q$.

###### keywords:

computational geometry, polygon nesting, polygon separation

##  1 Introduction

Figure 1:  Two sets of polygons in the plane (left) with different colors
(green and yellow). The yellow set effectively acts as an outer polygon with
holes. Separating the two sets with, possibly intersecting, individual fences
(middle) can lead to significantly more links in the fences (here 16) than
grouping same-colored polygons (right), which achieves this with just seven
links.

In the geometric multicut problem [2], we are given $\kappa$ disjoint sets of
polygons in the plane, each with a different color, and are asked for a
subdivision of the plane such that no cell of the subdivision contains
multiple colors. The goal is to minimize the total length of the subdivision
edges.

A different kind of separation is achieved in the polygon nesting problem [4],
where for two polygons $P$ and $Q$ with $P\subset Q$ one asks for a polygon
$P^{\prime}$ with the smallest number of links, s.t. $P\subset
P^{\prime}\subset Q$. There exists a series of work that addressed the
algorithmic complexity of nesting problems for various polygon families [4, 9,
13, 5, 12]. See Section 1.2 for more detail.

In this paper, we consider a variant of geometric multicut inspired by polygon
nesting, where we separate the sets from each other with a set of closed
polygon boundaries called _fences_ , which enclose only polygons of one color
and have the smallest possible number of links. If one or more sets are not
connected, we need to solve the combinatorial problem of choosing which
polygons should be grouped in each fence. Figure 1 illustrates the problem.
Some variants of the fencing problem already become NP-hard for point objects
with two colors, e.g., if we require the fence to be a single closed curve
[6].

In this paper, we assume the input sets are collections of polygons, one color
covers the plane minus a single polygonal hole (the outer polygon, a parallel
to polygon nesting), and we will focus on the case $\kappa=2$ of two colors.
We use $n$ to denote the total number of corners of the input polygons. Even
in this simple setting the problem turns out to be non-trivial. If both sets
are connected, then the problem is equivalent to finding a minimal nested
polygon, which can be solved in $O(n\log n)$ time [3]. If both sets are not
connected we show this problem to be NP-hard in Section 2. Note the contrast
to the geometric multicut problem, which is polynomially solvable for
$\kappa=2$ [1] but becomes -hard when $\kappa=3$ [2]. In Section 3 we show
that, when restricting every fence to contain at most two polygons, the
problem admits an -algorithm when parameterized by the maximal number of
segments per fence, a result which holds for any $\kappa$. Finally, in Section
4, we show that the problem is polynomial-time solvable if the convex hull of
the second color (the inner polygons) is contained in the outer polygon and
the first color is connected.

###  1.1 Problem Definition

Throughout this paper we consider polygons in $\mathbb{R}^{2}$ without self-
intersections but potentially with holes. Moreover, we consider a polygon as
the boundary together with its interior, unless stated otherwise. We consider
the following problem.

######  Definition 1.1 (Minimum Link Fencing (MLF)).

We are given $n$ pairwise interior-disjoint polygons
$\mathcal{P}=\\{P_{1},\ldots,P_{\color[rgb]{0,0,0}{|\mathcal{P}|}}\\}$ in the
plane, with a coloring function
$f:\mathcal{P}\rightarrow\\{1,\dots,\kappa\\}$, which assigns a color to every
input polygon. We write $\mathcal{P}_{i}=\\{P\mid f(P)=i\\}$. We want to find
a set of simple closed polygon boundaries
$\mathcal{F}=\\{{F_{1}},\ldots,{F_{m}}\\}$ such that the total number of links
$|F|$ on the boundary of $F=\bigcup_{i=1}^{k}{F_{i}}$ is minimized and if two
polygons $P_{a}$ and $P_{b}$ are enclosed by the same fence or are both in
$\mathbb{R}^{2}\setminus\bigcup_{i=1}^{k}\overline{F_{i}}$, where
$\overline{F_{i}}$ is the polygon bounded by $F_{i}$, then
$f(P_{a})=f(P_{b})$. We call $F_{i}$ a fence and $\mathcal{F}$ a _minimum link
fencing_ of $\mathcal{P}$.

Note the important difference in Definition 1.1 between $\mathcal{F}$, which
is the set of all fences of a solution, and $F$, which is the union over all
fences, i.e., one ( possibly disconnected) polygon. Thus $|\mathcal{F}|$ is
the number of fences and $|F|$ is the number of all segments in these fences.

(a) BMLF

(b) SMLF

(c) CMLF

Figure 2: Different problem inputs corresponding to (a) BMLF, (b) SMLF and (c)
CMLF. In (b) and (c) the convex hull of all input polygons indicated in gray.

Throughout the paper we refer to
$\mathbb{R}^{2}\setminus\bigcup_{i=1}^{|\mathcal{P}|}P_{i}$ as the _free
space_ (between polygons). We refer to $\mathcal{P}$, which contains polygons
of $\kappa$ different colors, as $\kappa$-colored and to the problem setting
as the $\kappa$-colored problem. We consider several problem variations.

If there exists a polygon $Q\in\mathcal{P}$ which is unbounded in every
direction, i.e. $\mathbb{R}^{2}\setminus Q$ is finite, this polygon $Q$
effectively acts as an outer boundary. In this case we call the problem
Bounded Minimum Link Fencing (BMLF). We denote the polygon $Q$ as the _outer
polygon_.  As a consequence, the size of the outer polygon automatically
bounds the length of any link in a fence. Else, in general, one fence could
conain a very long link, while retaining small complexity  when counting the
number of links only. Note that $Q$ can be emulated in an instance of Minimum
Link Fencing, by adding a large rectangular polygon
$P_{c}\setminus(\mathbb{R}^{2}\setminus Q)$, i.e., a large rectangle, of which
the area, which did not belong to $Q$ is cut out (light blue channel in Figure
2(a)). If $Q$ is the only polygon of its color $f(Q)$ we call this setting
Simply Bounded Minimum Link Fencing (SMLF). Moreover, if in an instance of
SMLF we have $CH(\bigcup_{i=1}^{\kappa}\mathcal{P}_{i}\setminus
Q)\subset\mathbb{R}^{2}\setminus Q$, i.e., the convex hull of all input
polygons except $Q$ does not intersect $Q$, we speak of Convex Bounded Minimum
Link Fencing (CMLF). The differences are illustrated in Figure 2.

###  1.2 Related Work.

Despite the fact that the problem is natural and fundamental, little previous
work exists. The problem of _enclosing_ a set of objects by a shortest system
of fences has recently been considered with a single set $B_{1}$ [1]. The task
is to “enclose” the components of $B_{1}$ by a shortest system of fences. This
can be formulated as a special case of our problem with $\kappa=2$ colors: We
add an additional set $B_{2}$, far away from $B_{1}$ and large enough so that
it is never optimal to surround $B_{2}$. Thus, we have to enclose all
components of $B_{1}$ and separate them from the unbounded region. In this
setting, there will be no nested fences. Abrahamsen et al. [1] gave an
$O(n\;\text{polylog}\;n)$-time algorithm for inputs that consist of $n$ unit
disks.

Some variations with additional constraints on the fence become -hard already
for point objects with two colors. For example, if we require the fence to be
a single closed curve, it has been observed by Eades and Rappaport [6] already
in 1993 that one can model the Euclidean Traveling Salesman Problem of
computing the shortest tour through a given set of sites by placing two tiny
objects of opposite color next to each site. If we require the fence to be
connected, the same construction will lead to the Euclidean Steiner Tree
Problem, which was shown to be -hard by Garey et al. in 1977 [8].

Polygon Nesting & Separation. Polygon nesting is considered to be a
fundamental problem in computational geometry, and has been extensively
studied since its inception. Aggarwal et al. [4] considered the problem of
finding a polygon nested between two given convex polygons that has a minimal
number of vertices. They gave an $O(n\log k)$ time algorithm for solving the
problem, where $n$ is the total number of vertices of the given polygons, and
$k$ is the number of vertices of a minimal nested polygon. Das [5] considered
a variant of MLF in his thesis, which restricts every fence to enclose exactly
one polygon, and showed that the problem is -hard. Given a polygon $Q$ of $m$
vertices inside another polygon $P$ of $n$ vertices, Ghosh [9] gave an
$O((n+m)\log k)$ time algorithm for constructing a minimum nested convex
polygon, where $k$ is the number of vertices of the output polygon, improving
upon the $O((n+m)\log(n+m))$ time algorithm of Wang and Chan [14]. However, on
the other hand, given a family of disjoint polygons $P_{1},P_{2},\ldots,P_{k}$
in the plane, and an integer parameter $m$, it is NP-complete to decide if the
$P_{i}$’s can be pairwise separated by a polygonal family with at most $m$
edges. Mitchell and Suri [12] presented efficient approximation algorithms for
constructing separating families of near-optimal size.

Full proofs of statements marked by ($\star$) are found in the Appendix.

##  2 Two-colored BMLF is -hard

In this section we will call polygons of color 1 _boundary polygons_ and
polygons of color 2 _inner polygons_. An instance of planar $3,4$-consists of
a Boolean CNF-formula $\phi$ with a set of variables
$\mathcal{V}=\\{v_{1},\dots,v_{n}\\}$ and a set of clauses $\mathcal{C}\subset
2^{\mathcal{V}}$, s.t. every clause is a disjunction of three literals and
every variable occurs at most four times as a literal in a clause.
Additionally, we are given the embedded plane incidence graph
$G_{\phi}=(\mathcal{V}\cup\mathcal{C},E)$, where $E=\\{vc\mid
v\in\mathcal{V},c\in\mathcal{C},v\text{ occurs as a literal in }c\\}$.  It is
known that deciding if a $3,4$\--formula has a satisfying assignment is
-complete [11].

Given an instance of planar $3,4$\- we create an instance of 2-colored BMLF
$\mathcal{P}$, emulating the shape of $G_{\phi}$ with one unbounded outer
polygon $Q$ and multiple boundary polygons of the same color $f(Q)=1$ (Figure
3), s.t. $\phi$ is satisfiable if and only if there exists a minimum link
fencing for $\mathcal{P}$ with at most a certain fixed number of total
segments.

Note that each gadget is described as a basic construction of gray polygons,
in which inner polygons are placed. This is possible, because we will invert
all gray polygons at the end of the reduction, s.t. the area of their union
makes up exactly the actual free space of our entire construction, see Figure
3. Stating that fences are computed inside the gray polygons should be
understood as fences being placed in the free space between polygons.
Throughout this reduction we distinguish fences based on the inner polygons
they include. We call two fences $F$ and $F^{\prime}$ _congruent_ , if and
only if they enclose the same set of inner polygons. We call two fencings
$\mathcal{F}$ and $\mathcal{F}^{\prime}$ _congruent_ if there is a bijective
mapping $f:\mathcal{F}\rightarrow\mathcal{F}^{\prime}$, s.t., every
$F\in\mathcal{F}$ is congruent to $f(F)\in\mathcal{F}^{\prime}$.

Let $\mathcal{P}$ be an instance of BMLF and $S_{1}$, $S_{2}$, and $S_{3}$
disjoint connected subsets of
$\mathbb{R}^{2}\setminus\cup_{P\in\mathcal{P}}P$. We call the ordered set
$\mathcal{S}=\\{S_{1},S_{2},S_{3}\\}$ a _non-collinear triple_ if there are no
three points $p_{1}\in S_{1}$, $p_{2}\in S_{2}$, and $p_{3}\in S_{3}$ such
that the straight-line segment $s$ from $p_{1}$ to $p_{3}$ contains $p_{2}$
and $s$ lies completely inside
$\mathbb{R}^{2}\setminus\cup_{P\in\mathcal{P}}P$. The choice of $S_{2}$ only
matters if there exists a straight-line segment in
$\mathbb{R}^{2}\setminus\cup_{P\in\mathcal{P}}P$ connecting points in $S_{1}$
and $S_{3}$. Therefore we can often omit $S_{2}$ from the description of the
triple or assume it as arbitrarily chosen. We call $S_{2}$ the _bend-set_ of
$\mathcal{S}$. Let $\mathcal{F}$ be a fencing of $\mathcal{P}$, and $S_{1}$,
$S_{2}$, and $S_{3}$ a non-collinear triple. We say a fence $F\in\mathcal{F}$
_crosses_ the triple $\\{S_{1},S_{2},S_{3}\\}$ if the boundary of $F$ contains
at least one point $p_{i}$ from each set $S_{i}$ for $i=1,2,3$ and there is a
cyclic traversal of the boundary of $F$ in which we see first $p_{1}$, then
$p_{2}$ and finally $p_{3}$. We write $]S_{1},S_{3}[$ to denote the part of
the boundary of $F$ that lies in between $p_{1}$ and $p_{3}$ and contains
$p_{2}$.

Any fence in a fencing for an instance of BMLF crossing a non-collinear triple
$\\{S_{1},S_{2},S_{3}\\}$ contains at least one bend in the interval
$]S_{1},S_{3}[$.

For $t>0$ let $\mathcal{S}_{1},\ldots,\mathcal{S}_{t}$ be non-collinear
triples that are crossed by a fence $F$ of a fencing $\mathcal{F}$ for some
instance of BMLF. Let $\mathcal{S}_{i}=\\{S_{j},S_{j+1},S_{j+2}\\}$ for
$i=1,\ldots,t$ and $j=3(i-1)+1$. We say that the triples are crossed by $F$
_in-order_ if there exist points $p_{i}$ on $F$ such that $p_{i}$ is in the
bend-set of $\mathcal{S}_{i}$ and there exists a cyclic traversal of $F$ in
which we see the points $p_{i}$ in order of their indices. Without loss of
generality we will assume throughout that when $F$ crosses
$\mathcal{S}_{1},\ldots,\mathcal{S}_{t}$ in-order it always crosses for some
$\mathcal{S}_{i}$ first the set $S_{i}$, then the bend-set $S_{i+1}$, and
finally $S_{i+2}$. We write $]S_{a},S_{b}[$ with $a<b$ and $a=1,\ldots,3t-1$
for the part of the boundary of $F$ that lies between a point $p_{a}\in S_{a}$
and $p_{b}\in S_{b}$ such that there exist points $p_{a},\ldots,p_{b}$ with
$p_{i}\in S_{i}$ that we see in this order in a cyclic traversal of $F$. For a
segment $s$ of $F$ we say it is _completely_ contained in $]S_{a},S_{b}[$ if
the start- and endpoint of $s$ are contained in $]S_{a},S_{b}[$ for any choice
of points $p_{a}$ and $p_{b}$.

Figure 3: A (schematized) complete construction for a small instance
$(v_{1}\lor v_{2}\lor\neg v_{3})\land(v_{1}\lor v_{3}\lor v_{4})$. The
incidence graph is shown in the top right. Fences are highlighted in green.
Also note that the boundary polygons make up most of the available area
including an unbounded outer polygon $Q$ as shown in the bottom right corner.
For better readability, we will invert these colors in all subsequent figures.

We say two non-collinear triples $\mathcal{S}=\\{S_{1},S_{2},S_{3}\\}$ and
$\mathcal{S}^{\prime}=\\{S_{1}^{\prime},S_{2}^{\prime},S_{3}^{\prime}\\}$ are
_non-overlapping_ if there exist no two segments that intersect all six
elements of $\mathcal{S}\cup\mathcal{S}^{\prime}$ in order $S_{1}$, $S_{2}$,
$S_{3}$, $S_{1}^{\prime}$, $S_{2}^{\prime}$, $S_{3}^{\prime}$. In other words
we require at least three different straight-line segments to connect a point
$p_{1}\in S_{1}$ with a point $p_{6}\in S_{3}^{\prime}$ and containing points
$p_{2}\in S_{2}$, $p_{3}\in S_{3}$, $p_{4}\in S_{1}^{\prime}$, and $p_{5}\in
S_{2}^{\prime}$ in order of their indices. Observe that by this definition the
non-collinear triples $\\{S_{1},S_{2},S_{3}\\}$ and its reverse
$\\{S_{3},S_{2},S_{1}\\}$ are non-overlapping. For a sequence of non-collinear
triples $\mathcal{S}_{1},\ldots,\mathcal{S}_{t}$ we say that the triples are
non-overlapping if $S_{i}$ is non-overlapping with $S_{i+1}$ for
$i=1,\ldots,t+1\mod t$.

Observation 2 together with the definition of non-overlapping gives the
following. Any fence in a fencing for an instance of BMLF crossing $t>0$ non-
overlapping non-collinear triples
$\mathcal{S}_{i}=\\{S_{j},S_{j+1},S_{j+2}\\}$ for $i=1,\ldots,t$ and
$j=3(i-1)+1$ in-order contains at least $t$ bends and therefore at least $t-1$
complete straight-line segments. in the interval $]S_{1},S_{3t}[$.

We can now show a lower bound for the number of links a minimum-link fence
uses in any solution of a BMLF instance. The lower bound essentially follows
from Observation 2 after observing that the segment closing the fence can
never reuse one of the $t-1$ segments that lie completely inside the sequence
of non-collinear triples.

######  Lemma 2.1.

Let $\mathcal{P}$ be an instance of BMLF and $\mathcal{F}$ a minimum-link
fencing for $\mathcal{P}$, then any fence $F\in\mathcal{F}$ that crosses $t>0$
non-overlapping non-collinear triples in-order consists of at least $t$
straight-line segments.

######  Proof 2.2.

By Observation 2 the fence $F$ has at least $t-1$ straight-line segments
Assume $F$ has also exactly $t-1$ segments. Let
$\mathcal{S}_{1},\ldots,\mathcal{S}_{t}$ be the non-overlapping non-collinear
triples and $S_{1},\ldots,S_{3t}$ be the sets of the non-collinear triple in
the order in which $F$ crosses them as above. Since $F$ is a simple polygon
there exists a polygonal chain $C$ starting at some point in $S_{3t}$ and
ending at some point in $S_{1}$. By Observation 2 there are $t-1$ straight-
line segments which are completely contained in $]S_{1},S_{3t}[$ which implies
that $C$ must consist of segments that are also completely contained in
$]S_{1},S_{3t}[$.

Now, we charge every of the $t-1$ segments to the piece of $F$ that connects
for each $\mathcal{S}_{i}$ with $i=1,\ldots,t-1$ some point in $S_{i+1}$ with
some point in $S_{i+2}$. Since the triples are non-overlapping each such
connection also requires a distinct segment. Then, for the connection of
$S_{3t-1}$ and $S_{3t}$ we require at least one more segment. Let $s$ be the
segment charged to the connection of $S_{3t-4}$ to $S_{3t-3}$. If we could
extend this segment to also intersect $S_{3t}$ we would violate that
$\mathcal{S}_{t-1}$ and $\mathcal{S}_{t}$ are non-overlapping. Symmetrically
for the segment charged to $S_{2}$ and $S_{3}$. Consequently, we require at
least one more segment.

###  2.1 Variable gadget

(a) Variable gadget construction with $\varepsilon$-gaps.

(b) Fencing for _true_ -state.

(c) Fencing for _false_ -state.

Figure 4: The variable gadget and its two possible fencings.

Every variable gadget consists of eight _T-polygons_ (two per clause in which
the variable can occur). Figure 4(a) illustrates the construction; T-polygons
are marked in gray. Every T-polygon has an isosceles triangle as the arm of
the T (the horizontal part of the T shape) and a spike (alternatively called a
_true spike_ and a _false spike_) protruding from the arm and two consecutive
polygons overlap at the end of their arms. For every variable
$v\in\mathcal{V}$, we construct a variable gadget $\mathcal{G}(v)$ as a
circular arrangement of eight overlapping T-polygons.

For every pair of overlapping T-polygons $A$ and $B$, we place an inner
polygon $P$, s.t. $P\subset A\cap B$. Let us fix some $A$, $B$, and $P$ as
above, then we place $P$ such that its three corner points have only a very
small distance $\varepsilon>0$ to some corner point of $A\cap B$. All three
$\varepsilon$-length segments between a corner point of $P$ and the closest
corner point of $A\cap B$ have to be crossed by every fence enclosing $P$.

Crucially, the variable gadget has only two minimum link fencings. These two
states are shown in Figure 4. We associate the one shown in Figure 4(b) to the
variable gadget encoding the value _true_ and the one shown in Figure 4(c) to
encoding _false_.

######  Lemma 2.3.

There are exactly two minimum link fencings $\mathcal{F}_{t}$ and
$\mathcal{F}_{f}$ of the variable gadget, both of which will enclose only
triangles in the same T-polygon with each fence, resulting in a fencing with
$12$ links for the whole variable gadget, s.t. every other minimum link
fencing is congruent to either $\mathcal{F}_{t}$ or $\mathcal{F}_{f}$.

######  Proof 2.4.

To prove this lemma, we will first number the eight inner polygons of the
variable gadget $A_{1},\ldots,A_{8}$. Any fence inside the variable gadget can
include any combination of $k$ inner polygons. We will prove this lemma, by
enumerating for every $k\in\\{1,8\\}$ all possible (non-symmetric)
combinations of including these inner polygons; Note that technically a fence
is allowed to include non-consecutive inner polygons. Note that any fence has
to consist of at least 3 segments and clearly every inner polygon of
$\mathcal{G}(v)$ can be fenced alone with 3 segments. For any possible fence
including multiple inner polygons, we show the existence of a certain number
of non-overlapping non-collinear triples, which provide a lower bound on the
number of segments for such a fence. All triples and the resulting lower
bounds on the number of segments in fencings including all possible
combinations of 2 to 8 inner polygons are shown in Appendix B. Enumeration
shows that a fence $F$ including $k$ inner polygons, has the minimum amount of
segments, if and only if the indices of the contained inner polygons are
consecutive (assuming $A_{8}$ and $A_{1}$ to be consecutive). In particular,
such a fence including 2, 3, 4, 5, 6, 7 or 8 inner polygons, requires (and can
be realized with) 3, 6, 8, 11, 13, 16 and 18 segments, respectively.

First observe that there are exactly two minimum link fencings, which include
exactly two neighboring inner polygons in one fence, both consisting of 12
segments total, both are shown in Figures 4(b) and 4(c). We can therefore
exclude any fence including six or more inner polygons, since they clearly
require more segments by themselves, which immediately eliminates the
possibility of including 6 or more inner polygons in one fence. Any fence
including five inner polygons requires at least 11 segments and at least one
additional fence is needed, which increases the segment count to at least 14.
Any fence including four inner polygons requires at least 8 segments. If the
remaining four segments are fenced together, we require at least 16 segments.
If they include a group of three polygons, we require at least 14 segments. If
two remaining polygons are grouped, we require 11 segments, but at least one
more fence (14 segments in total) are needed and if all remaining polygons are
fenced alone, we need 20 segments in total.

Next if three segments are fenced together, we require 6 segments and have
five inner polygons left. We already know that no fence including four or more
segments can be part of a minimum link fencing. If three of the remaining five
polygons are grouped we arrive at a total of at least 12 segments, with at
least one more fence needed. If at most two polygons are grouped, we need at
least three more fences and arrive at a total of at least 15 segments.

Finally, polygons could be fenced individually. Clearly there must be an even
number of individually fenced polygons. If all eight polygons are fenced
alone, we reach at least 24 segments, for six inner polygons fenced alone we
get 18 segments, four individually fenced polygons lead to 12 with at least
one more fence needed. Two inner polygons being fenced alone require at least
6 segments, with at least three more fences needed for the six left over
polygons, which require at least 9 segments leading to a total of 15 segments.

Therefore only two minimum link fencings exist, which require exactly 12
segments, and they group two neighboring inner polygons pairwise. We call the
fencing, which groups inner polygons, which are both contained in a gray
triangle with a true spike $\mathcal{F}_{t}$ and the other $\mathcal{F}_{f}$.

###  2.2 Clause gadget

For every clause $c\in\mathcal{C}$ in which three variables
$v_{1},v_{2},v_{3}$ occur either as a positive or a negative literal, we
create a clause gadget $\mathcal{G}(c)$. A clause gadget consists of three
chains of an even number of gray triangles. These triangles are placed s.t.
their hypotenuses intersect at an angle of at most $\pi$ as shown in Figure
5(a). The triangles are sufficiently long and thin, s.t., we can define two
sets in every gray triangle (one to either side of the central line), s.t.,
the second set $a^{\prime}$ of the $i$-th triangle and the first set $b$ of
the $(i+1)$-th triangle form a non-collinear triple. By construction the non-
collinear triple between the $(i-1)$-th and the $i$-th triangle and the one
between the $i$-th and the $(i+1)$-th triangle are non-overlapping.

We place the three chains such that the three first triangles of the chains
have a common intersection. Moreover, they intersect in such a way that their
hypotenuses pairwise form $\frac{2\pi}{3}$ angles (Figure 5(b)). The last gray
triangle of the first, second and third chain intersect a spike of
$\mathcal{G}(v_{1})$, $\mathcal{G}(v_{2})$ and $\mathcal{G}(v_{3})$,
respectively. They intersect a true or false spike if the variable occurs as a
positive or negative literal, respectively. We refer to each chain of gray
polygons as a _wire_. The _length_ of a wire is the number of gray triangles
in its corresponding chain.

Let $W_{1}$, $W_{2}$, and $W_{3}$ be the wires of a clause gadget
$\mathcal{G}(c)$ for clause $c$, where $W_{i}$ intersects the spike of
$\mathcal{G}(v_{i})$ for $i\in\\{1,2,3\\}$. We place an inner triangle,
denoted the _clause triangle_ $B_{c}$ of $\mathcal{G}(c)$, in the overlap of
$W_{1}$, $W_{2}$, and $W_{3}$. Moreover, for wire $W_{i}$ with gray triangles
$T^{i}_{j}$ we place inner triangles $B^{i}_{j}$ in the overlap of the $j$-th
and $(j+1)$-th gray triangle of the respective wire and a final triangle in
the intersection with the spike of $\mathcal{G}(v_{i})$. In the following we
write $T_{1},\ldots,T_{k}$ for the gray triangles and $B_{1},\ldots,B_{k}$ for
the inner polygons of one wire $W_{i}$, if $i$ is clear from the context.
Hence, inner triangle $B_{i}$ is contained in the gray triangles $T_{i}$ and
$T_{i+1}$ and gray triangle $T_{i}$ for $i>1$ contains the inner triangles
$B_{i}$ and $B_{i+1}$.

(a)

(b)

Figure 5: Wires are constructed from consecutive gray triangles places such
that two consecutive triangles always contain a non-collinear triple, which
are pairwise non-overlapping.

Let $B_{1},\ldots,B_{k}$ be the inner polygons of a wire and $F$ a fence
containing $B_{i}$ and $B_{j}$ for some $i<j-1$ and $i=1,\ldots,k-2$ but not
$B_{z}$ for $i<z<j$, then we say $F$ _bypasses_ $B_{z}$. For indices $1\leq
i_{1}<i_{2}<j_{1}<j_{2}\leq k$, we say two fences $F_{1}$ and $F_{2}$
containing some polygons of the wire _interleave_ if $B_{i_{1}}$ and
$B_{j_{1}}$ are in $F_{1}$ and $F_{1}$ bypasses $B_{i_{2}}$ as well as
$B_{i_{2}}$ and $B_{j_{2}}$ are in $F_{2}$ and $F_{1}$ bypasses $B_{j_{1}}$.

Let $F$ be a fence of a minimum link fencing $\mathcal{F}$ for a clause gadget
$\mathcal{G}(c)$. Let $s$ be a segment contained in the union of the gray
triangles that form $\mathcal{G}(c)$ such that $F$ crosses $s$ in two points
$p$ and $q$. Then _splitting_ $F$ at $s$ means the following. Delete $F$ in an
$\varepsilon$-region around $p$ and $q$ this creates two polygonal-chains, say
$F^{\prime}$ and $F^{\prime\prime}$ with endpoints $p^{\prime}$ and
$q^{\prime}$ on one side of $s$ and $p^{\prime\prime}$ and $q^{\prime\prime}$
on the other. Connect $p^{\prime}$ with $q^{\prime}$ and $p^{\prime\prime}$
with $q^{\prime\prime}$ to form the two new fences $F^{\prime}$ and
$F^{\prime\prime}$. Clearly, $|F^{\prime}|+|F^{\prime\prime}|=|F|+2$.

#### One isolated wire

For the following we fix an arbitrary clause $c$. Let $\mathcal{G}(c)$ be the
clause gadget of $c$ and $W$ one of the wires of $\mathcal{G}(c)$ with inner
polygons $B_{1},\ldots,B_{k}$. We denote as _isolated wire_ the gray triangles
of the chain of $W$ that do not contain the clause triangle.

We are interested in how a minimum link fencing of an isolated wire looks
like. Crucially, we first show that a fence of a minimum link fencing of an
isolated wire cannot bypass any inner polygon of an inner polygon.

######  Lemma 2.5 ($\star$).

A minimum link fence $\mathcal{F}$ of an isolated wire $W$ of $\mathcal{G}(c)$
does not contain a fence $F\in\mathcal{F}$ such that $F$ bypasses an inner
polygon $B_{i}$ with $i\in\\{2,\ldots,k-1\\}$ of $W$.

In the following we are going to bound the number of consecutive polygons that
are contained in one minimum link fence of an isolated wire. We compare this
then to a fence containing all inner polygons of an isolated wire. Such a
fence, by construction, contains $2z$ non-collinear triples and hence requires
$2z$ segments by Lemma 2.1. Figure 6 shows these triples. Constructing such a
fence is straight-forward by following these non-collinear triples. The
following lemma summarizes this statement.

######  Lemma 2.6.

Let $\mathcal{F}$ be a minimum link fencing of an isolated wire $W$ of
$\mathcal{G}(c)$, any fence $F\in\mathcal{F}$ that contains $z>2$ consecutive
inner polygons of $W$ has at least $2z$ segments and such a fence exists.

######  Lemma 2.7.

Let $\mathcal{F}$ be a minimum link fencing of an isolated wire $W$ of
$\mathcal{G}(c)$, then every fence of $\mathcal{F}$ contains at most three
consecutive inner polygons.

######  Proof 2.8.

Let $B_{1},\ldots,B_{k}$ be the inner polygons of $W$. By Lemma 2.5 we can
assume that the inner polygons of $W$ contained in $F$ are consecutive in the
sequence of inner polygons. Let $F\in\mathcal{F}$ be a fence containing $z>3$
inner polygons of $W$.

By Lemma 2.6 we know that $F$ consists of $2z$ segments. We replace $F$ with a
fence $F_{1}$ including the two first polygons included in $F$ and a fence
$F_{2}$ including all $z-2$ following inner polygons. Again by Lemma 2.6 it
follows that $|F_{2}|=2z-4$ and it holds that $|F_{1}|=3$. In sum, we get that
$|F_{1}|+|F_{2}|=2z-4+3=2z-1\leq|F|$, a contradiction.

Figure 6: Non-colinear triples in a fence including a series of consecutive
inner polygons.

Lemmas 2.7 and 2.6 now lead to a characterization of minimum link fences of
isolated wires.

######  Lemma 2.9 ($\star$).

Let $\mathcal{F}$ be a minimum link fencing of an isolated wire $W$ of
$\mathcal{G}(c)$ with $k$ inner polygons, then $\mathcal{F}$ has in total
$3k/2$ segments and $F\in\mathcal{F}$ contains exactly two consecutive inner
polygons $B_{i}$ and $B_{i+1}$ for $i$ odd.

#### Integrating the clause triangle

So far we only considered one arbitrary isolated wire of $\mathcal{G}(c)$. To
put things together we need to consider the interaction of the three wires of
$\mathcal{G}(c)$. Specifically, we need to show that no fence in a minimum
link fencing of $\mathcal{G}(c)$ contains inner polygons from two different
wires.

We extend the definition of bypassing an inner polygon of a wire to a whole
clause gadget. Let $F$ be a fence for $\mathcal{G}(c)$, then $F$ _bypasses_ an
inner polygon $B_{j}^{i}$ of wire $W_{i}$ of $\mathcal{G}(c)$ if $F$ contains
the clause triangle $B_{c}$ or some inner polygon of a wire $W_{i^{\prime}}$
with $i^{\prime}\neq i$ and $F$ contains $B_{l}^{i}$ for wire $W_{i}$ with
$l>j$. We say $F$ _bypasses_ the clause triangle of $\mathcal{G}(c)$ if $F$
contains inner polygons of at least two different wires of $\mathcal{G}(c)$
but not the clause triangle $B_{c}$ of $\mathcal{G}(c)$.

As for an isolated wire we can show that no inner polygon for a whole clause
gadget can be bypassed. This can be seen after observing that no fence can
bypass the inner polygons of an isolated wire without violating Lemma 2.5. The
remainder of the proof is then a careful case enumeration, see Appendix A.2.

######  Lemma 2.10 ($\star$).

Let $\mathcal{F}$ be a minimum link fencing of $\mathcal{G}(c)$ and
$B_{1},\ldots,B_{k}$ the inner polygons of one of the wires of
$\mathcal{G}(c)$. Then there is no fence $F\in\mathcal{F}$ that bypasses an
inner polygon $B_{i}$ with $i\in\\{1,\ldots,k-1\\}$.

Finally, we show that no minimum link fence of a clause gadget can ever fence
two polygons that are in different wires. Again, this is shown essentially via
a case enumeration that considers how a minimum link fence includes the first
two to three polygons of each wire together with the clause triangle. In each
case we can conclude that there exists a fence with fewer segments that in
fact does not use the inner polygons of two distinct wires.

######  Lemma 2.11 ($\star$).

Let $\mathcal{F}$ be an optimal fencing of a clause gadget, then there exists
no fence $F\in\mathcal{F}$, which includes inner polygons belonging to two
different wires.

We can now use Lemma 2.11 to argue that the clause triangle is only included
in a fence together with inner polygons of at most one wire.  We say that such
a wire is in a _satisfying_ state. The other two wires should therefore, by
Lemma 2.9, only use fences including two inner polygons; leading to
$\frac{3(k_{a}+k_{b}+k_{c})}{2}+3$ segments in total ($k_{a},k_{b}$ and
$k_{c}$ being the number of inner polygons in the wires). If we include the
clause triangle in a fence of a wire, we get the same amount of segments,
however, we can choose fences, s.t., the last inner polygon of the wire which
fences the clause triangle, is fenced alone. This will be crucial in the
argument of how the wires and therefore the clause gadget interacts with the
variable gadget.

#### Interaction with the variable gadgets

It remains to describe the interaction between the variable and clause
gadgets. Depending on the state of the variable gadget we can fence the last
inner polygon of a wire in the fence of a variable gadget. We provide a fence
with 5 segments (i.e., two additional ones) for the case, where the variable
gadget is in the correct state and the existence of six non-collinear triples
for the other case, see Figure 7.

######  Lemma 2.12.

The last inner polygon of a wire can be included in a fence of the variable
gadget, whose spike it is connected to for the cost of two additional segments
if the variable gadget is in the correct state and at least three additional
segments otherwise.

(a) $\mathcal{G}(v)$ in correct state

(b) $\mathcal{G}(v)$ in incorrect state

Figure 7: If $\mathcal{G}(v)$ is in the correct truth state (a) inclusion of
the first inner polygon of $\mathcal{G}(v,c)$ induces an additional cost of
two links, otherwise (b) the additional cost is at least three.

Concluding the interaction between clause and variable gadget we show that
given a variable gadget is in the correct state w.r.t. a clause gadget we can
fence the inner polygons of the wires of a clause gadget using $3/2$ segments
per polygon and adding only two segments to the fence of the variable gadget.

######  Lemma 2.13 ($\star$).

If and only if at least one of the connected variable gadgets is in the
correct state, the clause gadget can be fenced with a total of
$\frac{3(k_{a}+k_{b}+k_{c})}{2}$ segments plus two additional segments to a
fence of the variable gadget, which is connected to the wire in the satisfying
state.

#### Correctness

It remains to argue the correctness of our reduction which then implies our
main theorem.

######  Theorem 2.14 ($\star$).

Two-colored BMLF is -hard even when restricting all fences to include at most
three polygons.

######  Proof 2.15 (Proof sketch).

For an instance $\phi$ of planar $3,4$-, we construct a variable gadget for
every variable and connect the clause gadgets accordingly. By construction any
fencing with $|\mathcal{V}|\cdot
12+\sum_{c\in\mathcal{C}}(\frac{3(k^{c})}{2}+2)$ segments, requires one wire
of every clause gadget to be in a satisfying state. The connected variable
gadget is forced into the true or false state, depending on the connected
spike. This implies a satisfying variable assignment for $\phi$.

Conversely, since every variable is either true or false and for every clause
there is a true literal, we can set all variable gadgets into the true or
false state according to the assignment and are guaranteed to be able to put
exactly one wire per clause gadget into a satisfying state for an additional
cost of exactly two.

##  3 An -algorithm for BMLF with at most two polygons in each fence

In Section 2 we showed that BMLF is -hard when there are only two colors, each
fence contains at most three polygons, and each fence consists of at most five
links. In contrast, we are going to show in this section that BMLF can be
solved in -time when parameterizing the problem by the maximum number of links
in any fence and allowing at most two polygons per fence, i.e., the problem
can be solved in polynomial-time when fixing the maximum number of links in
any fence and restricting each fence to contain at most two polygons.

For our algorithm we make use of the following result derived from the work of
Hershberger and Snoeyink [10]. It allows us to compute for a given _loop_ ,
i.e., a closed polygonal curve, inside a polygon with holes, a minimum-link
loop of the same homotopy in time $O(nk)$, where $n$ is the complexity of the
polygon and $k$ is the size of the resulting fence.

######  Theorem 3.1 (Derived from Section 5.2 [10]).

Given a polygon $P$ without self-intersections but potentially with holes of
complexity $n$, an integer $k$, and a loop $\alpha$ lying in the interior of
$P$ with $O(nk)$ corners, we can decide in time $O(nk)$ if there exists a loop
$\alpha^{\prime}$ of the same homotopy-class as $\alpha$ with at most $k$
links.

######  Remark 1.

It is worth noting that in the paper by Hershberger and Snoeyink [10] Theorem
3.1 is only stated in text. The runtime is given as
$O(C_{\alpha}+\Delta_{\alpha}+\Delta_{\alpha^{\prime}})$, where $C_{\alpha}$
is the complexity of $\alpha$, the free space between polygons is assumed to
be triangulated and $\Delta_{\alpha}$ and $\Delta_{\alpha^{\prime}}$ are the
number of triangulation edges intersected by $\alpha$ and the fence
$\alpha^{\prime}$, respectively. However an example of an instance with
multiple obstacles is given, in which $\Delta_{\alpha^{\prime}}\in\Omega(nk)$,
where $n$ is the number of corners over all polygons. Since in our scenario we
can find a path $\alpha$ s.t. $C_{\alpha}\in O(nk)$ and $\Delta_{\alpha}\in
O(nk)$, we can make the assumption that $\alpha^{\prime}$’s complexity is in
$O(nk)$.

Let $P$ be a polygon without self-intersections. We denote with
$\mathcal{T}_{P}=\\{T_{1},\ldots,T_{z}\\}$ a triangulation of $P$ with
triangles $T_{1},\ldots,T_{z}$. Note that we do not require any further
properties of $\mathcal{T}_{P}$. If $P$ is clear from the context we omit it
and set $\mathcal{T}=\mathcal{T}_{P}$. Let $T_{1},T_{2}\in\mathcal{T}$ be two
triangles and let $l$ be a line segment with endpoints $p$ and $q$ such that
$p\in T_{1}$ and $q\in T_{2}$. We call $l$ a _splitting segment_. Consider
Figure 8(a) for an example for $T_{1}$ and $T_{2}$ if $l$ contains no points
of $\mathbb{R}^{2}\setminus P$. Intuitively, a splitting segment separates the
holes that intersect the convex hull of $T_{1}\cup T_{2}$ into two sets. Let
$\mathcal{H}$ be all the holes of $P$ that intersect or are fully contained in
the interior of the convex hull of $T_{1}\cup T_{2}$. We say that a hole
$H\in\mathcal{H}$ is to the _left_ (_right_) of $l$ if the from $p$ to $q$
oriented supporting line of $l$ leaves $H$ in the left (right) half-plane. We
call two splitting segments of $T_{1}$ and $T_{2}$ _equivalent_ if the same
holes of $\mathcal{H}$ are to their respective left and right. Segments which
intersect holes are not splitting segments.

######  Lemma 3.2.

Let $P$ be a polygon without self-intersection, $\mathcal{H}$ a set of holes
and $\mathcal{T}$ a triangulation of $P$. Then for every pair of triangles
$T_{1},T_{2}\in\mathcal{T}$ with $T_{1}\neq T_{2}$ there are at most
$4|\mathcal{H}|^{2}$ different equivalence classes of splitting segments.

######  Proof 3.3.

Let $\mathcal{H}^{\cap}\subseteq\mathcal{H}$ be the set of holes, which
intersect the joint convex hull $C$ of $T_{1}$ and $T_{2}$ or are fully
contained in it. Let $l$ be a splitting segment with endpoints $p\in T_{1}$
and $q\in T_{2}$. Observe, that since $l$ is completely contained in
$C-\mathcal{H}$ we, by definition of equivalent splitting segments, can
disregard any hole $H\not\in\mathcal{H}^{\cap}$.

Let $l\in C$ be a splitting segment of $T_{1}$ and $T_{2}$, which has a set
$L\subseteq\mathcal{H}^{\cap}$ of holes to its left and a set
$R\subseteq\mathcal{H}^{\cap}$ to its right. There exists another splitting
segment $l_{c}$ whose supporting line is a bitangent on two holes, say
$H_{L}\in L$ and $H_{R}\in R$, such that $l_{c}$ has also $L$ to its left and
$R$ to its right. We obtain the splitting segment $l_{c}$ from $l$ by rotating
$l$ first around its center point until it touches either $H_{L}$ or $H_{R}$
in a point $r$ and then continue to rotate $l$ around $r$ until it touches the
second hole, see Figure 8(a). Since any pair of holes has at most four
bitangents (Figure 8(b)) there are at most $4|\mathcal{H}^{\cap}|^{2}$
equivalence classes.

(a) A splitting segment $l_{c}$ equivalent to $l$ and bitangent to two holes.

(b) Bitangents

Figure 8:  (a) We can obtain the splitting segment $l_{c}$ from a splitting
segment $l$ by rotating $l$ clockwise until it is a bitangent to two holes.
(b) Any pair of two polygons admits at most four bitangents, only one of which
can not be rotated clockwise without intersecting one of the polygons.

######  Theorem 3.4.

Given an instance $\mathcal{P}$ of BMLF with outer polygon $Q\in\mathcal{P}$,
we can decide in time $O(kn^{2k+4})$ if a minimum link fencing $\mathcal{F}$
of $\mathcal{P}$ exists, in which every fence contains at most two polygons,
each fence in the fencing has at most $k$ segments, and $n$ is the number of
corners in $\mathcal{P}$.

######  Proof 3.5.

Throughout, we consider the triangulation $\mathcal{T}$ of the free space of
$\mathcal{P}$. Let $t+1$ be the number of colors in the given instance and
$c_{1},\ldots,c_{t}$ be the colors of polygons in $\mathcal{P}$ with
$c_{i}\neq f(Q)$ for all $i=1,\ldots,t$.

Observe that the homotopy of a fence including exactly one polygon
$P\in\mathcal{P}$ is unique. We find a path $\alpha$ with this homotopy in the
triangulated free space between the polygons in $\mathcal{P}$ by traversing
the boundary of $P$ clockwise and at every corner of the polygon adding every
incident triangle of $\mathcal{T}$ in clockwise order to a list. This yields a
series of triangles from which we can construct a loop $\alpha$ such that $P$
is contained in $\alpha$. This can be done, for example, by connecting all
midpoints of triangulation segments of a triangle and its successor in the
loop. Then, we use Theorem 3.1 to obtain a minimum-link fence for $P$ from
$\alpha$ or determine that no fence with at most $k$ links exists. Computing
all individual fences requires $O(|\mathcal{P}|kn)=O(kn^{2})$ time.

Next, we consider every pair $P_{1},P_{2}\in\mathcal{P}$ with $P_{1}\neq
P_{2}$, $c_{i}=f(P_{1})=f(P_{2})$ and $i\in\\{1,\ldots,t\\}$. Note that in
contrast to a fence containing only one polygon, a fence containing exactly
two polygons can belong to several different homotopy-classes w.r.t. the
remaining polygons.

Now, we describe how to compute a minimum-link fence $F$ for two polygons
$P_{1}$ and $P_{2}$ of $\mathcal{P}$. Recall that all polygons in
$\mathcal{P}$ together have $n$ corners. Since we have only $O(n)$ triangles
in $\mathcal{T}$ we can iterate over all possible $O({n\choose k})\in
O(n^{k})$ ordered tuples of $k$ triangles. Fix in the following such an
ordered $k$-tuple $(T_{1},\ldots,T_{k})$ of triangles in $\mathcal{T}$. There
are only $O(|\mathcal{P}|^{2})$ many non-equivalent splitting segments
connecting points in triangles $T_{i}$ and $T_{i+1}$ by Lemma 3.2.
Consequently, we can iterate over the $O((|\mathcal{P}|^{2})^{k})=O(n^{2k})$
many different combinations of splitting segments between consecutive
triangles. In case there are two consecutive triangles between which no
possible splitting line exists we reject this tuple of triangles. Assume in
the following that we fix for every pair $T_{i}$ and $T_{i+1}$ a splitting
segment $l_{i}$.

It remains to construct a plane loop $\alpha$ as input for the algorithm of
Hershberger and Snoeyink [10] or decide that no such loop exists for the fixed
choices of triangles and splitting segments. From the triangles
$T_{1},\ldots,T_{k}$ and the splitting segments $l_{1},\ldots,l_{k}$ we derive
a sequence of triangles $\tau_{1},\ldots,\tau_{z}$ of $\mathcal{T}$ that
$\alpha$ has to visit. Since the triangulation $\mathcal{T}$ is defined by the
corners of polygons in $\mathcal{P}$ each splitting segment $l_{i}$ gives rise
to a unique sequence of triangles. We concatenate all these sequences starting
with the sequence induced by $l_{1}$ to obtain the sequence
$\Theta=(\tau_{1},\ldots,\tau_{z})$. Observe, that triangles along this
sequence may repeat and that $\tau_{1}=\tau_{z}$.

It remains to decide if there exists a plane loop $\alpha$ visiting each
triangle of $\Theta$ in order. To make the following description simpler let
$s_{i}$ be the shared boundary of $\tau_{i}$ and $\tau_{i+1}$. If for no $i$
with $i\in\\{1,\ldots,z-1\\}$, we find that $s_{i}=s_{i+1}$ we create a loop
$\alpha$ by connecting the centerpoint of $s_{i}$ with the one of $s_{i+1}$.
Since no boundary repeats, this is always possible without any centerpoint and
hence triangle being used twice. Finally, we add the segment from the
centerpoint of $s_{z}$ to the centerpoint of $s_{1}$ which is also always
possible as $\tau_{1}=\tau_{z}$.

Now assume there exist at least two indices $i$ and $j$ with $i\neq j$ and
$i,j\in\\{1,\ldots,z\\}$ such that $s_{i}=s_{j}$. Build the loop as before and
let $\alpha_{1},\ldots,\alpha_{z}$ be the segments in the constructed loop.
Since we allow repeated boundaries there exist subsequences among the
$\alpha_{1},\ldots,\alpha_{z}$ that are repeated. In the following we assume
that we only consider inclusion maximal repeated subsequences. Let
$A=\\{\alpha_{1}^{\prime},\ldots,\alpha_{a}^{\prime}\\}$ be one occurrence of
such a subsequence of the $\alpha_{i}$’s that is repeated at least once and
let $\hat{A}$ be a different occurrence. Let
$s_{1}^{\prime},\ldots,s_{a}^{\prime}$ be the subsequence of the $s_{i}$’s
that correspond to the triangle boundaries passed by the segments in $A$ and
$\hat{A}=\\{\hat{\alpha_{1}},\ldots,\hat{\alpha_{a}}\\}$. Now observe that in
a plane loop the vertices of $A$ and $\hat{A}$ have to always appear in the
same order along $s_{1}^{\prime},\ldots,s_{a}^{\prime}$. If they would not,
let $s_{i}^{\prime}$ and $s_{i+1}^{\prime}$ for $i\in\\{1,\ldots,a-1\\}$ be
two segments such that the vertices of $A$ and $\hat{A}$ on $s_{i}^{\prime}$
and $s_{i+1}^{\prime}$ are not in the same order. Without loss of generality
assume the vertex of $A$ on $s_{i}^{\prime}$ is above the one of $\hat{A}$ and
the opposite is true for $s_{i+1}^{\prime}$, then we find that $\alpha_{i}$
and $\hat{\alpha_{i}}$ cross. Hence, the only decision to make is to decide,
for each pair of repeated subsequences, in which order their vertices appear
along the corresponding triangle-boundaries. Since every repeated subsequence
implies an intersection between two segments $l_{i}$ and $l_{j}$ with $i\neq
j$ and $i,j\in\\{1,\ldots,k\\}$ we find that there are at most $k^{2}$ such
repeated sequences. Consequently, there are at most $2^{O(k)}$ possible ways
to distribute the center points in each shared part along the boundaries.

To sum up, for one pair of polygons $P_{1},P_{2}$ we have to consider
$O(n^{2k})$ possible non-homotopy equivalent fences and for each homotopy we
can check in $O(n^{2}\cdot 2^{k})$ if there exists a plane loop $\alpha$
realizing it, leading to a total runtime of $O(2^{k}\cdot n^{2k+2})$ to
enumerate every potential homotopy of a minimum link fence. For each of the
$O(n^{2k})$ different homotopies, we can use Theorem 3.1 to compute a minimum
link fence in $O(kn)$, hence we can compute a minimum link fences for all
pairs of polygons in $O(n^{2}\cdot kn^{2k+2})=O(kn^{2k+4})$.

If for any polygon no fence, alone or in a pair with another polygon, with $k$
or fewer links is found, we return that no solution exists. Otherwise, let
$\lambda_{uv}$ be the number of links for a minimum link fence containing
$P_{u},P_{v}\in\mathcal{P}$ and $\lambda_{u}$ the number of links for a
minimum link fence containing only $P_{u}\in\mathcal{P}$. Consider a complete
graph $G$ containing one vertex $u$ for each polygon $P_{u}\in\mathcal{P}$ and
one more vertex $x$ if $|\mathcal{P}|$ is odd. Set the edge-weights
$w(u,v)=\min\\{\lambda_{uv},\lambda_{u}+\lambda_{v}\\}$ and
$w(x,u)=\lambda_{u}$ for $P_{u},P_{v}\in\mathcal{P}$. If for some
$P_{u}\in\mathcal{P}$ or pair $P_{u},P_{v}\in\mathcal{P}$ no fence with $\leq
k$ segments existed we remove that edge.

To find a minimum-link fencing of $\mathcal{P}$ it now suffices to compute a
minimum weight perfect matching in $G$. Let $M$ be such a matching. Then, a
minimum link fencing $\mathcal{F}$ of $\mathcal{P}$ can be constructed from
$M$ in the following way. If $uv\in M$, we add the (pre-computed) minimum link
fences containing only $P_{u}$ and $P_{v}$ to $\mathcal{F}$ if the weight
$w(u,v)=\lambda_{u}+\lambda_{v}$ or the fence containing $P_{u}$ and $P_{v}$
if $w(u,v)=\lambda_{uv}$. If $|\mathcal{P}|$ was odd we also find an edge
$xu\in M$ and we add the fence containing only $P_{u}$ to the fencing.

Finding a minimum weight perfect matching in a general graph with $V$ vertices
and $E$ edges can be done for example in $O(V^{2}E)$ time via finding a
maximum weight perfect matching (e.g. [7]) in the same graph with edge weights
set to maximum edge-weight plus one minus the original edge-weight. Since $G$
has $O(|\mathcal{P}|)$ vertices and $O(|\mathcal{P}|^{2})$ edges we can
compute this matching in $O(|\mathcal{P}|^{4})=O(n^{4})$, which is dominated
by the initial computation of the minimum link fences.

##  4 An algorithm for two-colored CMLF

In this section we present an algorithm for solving two-colored CMLF.
Computing a minimum-link fence in this setting can be done by computing a
fence for the convex hull of the contained polygons with the algorithm by Wang
[13] which runs in time $O(n\log n)$ with $n$ being the number of corners of
the contained polygons. Throughout this section an instance of CMLF is given
as $(\mathcal{P},Q)$ where $Q$ is the outer polygon and $\mathcal{P}$ is the
set of polygons contained in $Q$.

Figure 9:  Computing a new fence (orange) from the old fences (purple) and the
convex hull (blue).

######  Lemma 4.1.

Given an instance $(\mathcal{P},Q)$ of two-colored CMLF, let $\mathcal{F}$ be
a solution for $(\mathcal{P},Q)$. There exists a solution
$\mathcal{F}^{\prime}$ for the two-colored CMLF instance $(CH(\mathcal{P}),Q)$
with $|F|=|F^{\prime}|$.

######  Proof 4.2.

As $F$ is a minimum-link fencing of $(\mathcal{P},Q)$, it suffices to consider
the case where a minimal link fencing of $(CH(\mathcal{P}),Q)$ has strictly
more segments than $|F|$. We will construct a new fence $F^{\circ}$ from this
instance. Let $(p_{1},\dots,p_{z})$ be the intersection points between $F$ and
$CH(\mathcal{P})$ ordered as they appear in a clockwise traversal of the
convex hull, and observe that $z$ is even. Let $p_{i}$, $p_{i+1}$ be pairs of
intersection points between $F$ and $CH(\mathcal{P})$ such that the straight-
line segment $s_{i}$ connecting $p_{i}$ and $p_{i+1}$ lies on
$CH(\mathcal{P})$ and completely outside of $F$ (see Figure 9). Consider the
supporting line $\ell_{i}$ of $s_{i}$. If the fence lies completely in one of
the closed half-planes bounded by $\ell_{i}$ we add $s_{i}$ to $F^{\circ}$.
Assume this is not the case. As $s_{i}$ is on $CH(\mathcal{P})$ we get that
$\ell_{i}$ does not intersect any polygon in $\mathcal{P}$. Moreover, as
$\mathcal{F}$ consists of closed simple polygons we find two intersection
points $p_{i}^{\prime}$ and $p_{i+1}^{\prime}$ that lie on $\ell_{i}$, s.t.,
the parts of $F$ appearing in a clockwise traversal from $p_{i}^{\prime}$ to
$p_{i}$, as well as the ones in a clockwise traversal from $p_{i+1}$ to
$p_{i+1}^{\prime}$ lie outside of $CH(\mathcal{P})$. We add the segment
$s_{i}^{\prime}$ between $p_{i}^{\prime}$ and $p_{i+1}^{\prime}$ to
$F^{\circ}$. Doing this for every pair of intersections we obtain a set of
segments $F^{\circ}$, where all segments are on the convex-hull of
$\mathcal{P}$. Note that it is possible for these segments to intersect; if
that is the case we only keep the parts until their intersection point.
Finally, the start and end-points of connected chains of segments in
$F^{\circ}$ lie on segments of fences in $\mathcal{F}$. We can convert
$F^{\circ}$ into a fence of $CH(\mathcal{P})$ by connecting these endpoints
along the fences in $\mathcal{F}$ and that fence will be disjoint from
$\mathcal{P}$ (except possibly touching $\mathcal{P}$ in corner points).

It remains to argue that indeed $|F^{\circ}|\leq|F|$. We partition $F^{\circ}$
into two categories, segments that coincide with segments in $F$ and segments
that do not. Each of them is either a full segment of $F$ or originates from
the intersection of at most two different $s_{i}^{\prime}$’s and a segment of
$F$. Furthermore, we add $z/2$ segments $s_{i}^{\prime}$ that are not sub-
segments of segments in $F$. For each such $s_{i}^{\prime}$ we find at least
one segment of $F$ for which we did not add any sub-segment to $F^{\circ}$.
These are the segments of $F$ on which $p_{i}$ and $p_{i+1}$ lie or that are
fully outside of $F^{\circ}$.

######  Theorem 4.3.

Two-colored CMLF can be solved in time $O(n\log n)$ where $n$ is the number of
corners of polygons in $\mathcal{P}$.

##  5 Conclusion

We have shown BMLF to be -hard even if every fence contains at most three
polygons, each fence has at most five links, and only two different colors of
polygons are present. Our reduction holds regardless of requiring disjoint
fences or not. Note, that our reduction can be adapted to not require the
outer bounding polygon $Q$. Instead, we can replace $Q$ by one polygon with a
narrow and very complex channel, connecting the “inside” with the “outside”.
On the algorithmic side, we gave an -algorithm for BMLF parameterized by the
maximum number of links in a fence and allowing at most two polygons per
fence. We also showed that two-colored CMLF can be solved in polynomial time.

It is open if one can eliminate the exponential dependency on the number of
links in our algorithm for BMLF. Furthermore, while our reduction holds when
replacing the outer bounding polygon, our algorithm does not since we cannot
immediately apply Theorem 3.1. Similarly, requiring the fences to be disjoint
for BMLF is an interesting open direction.

## References

  * [1] Mikkel Abrahamsen, Anna Adamaszek, Karl Bringmann, Vincent Cohen-Addad, Mehran Mehr, Eva Rotenberg, Alan Roytman, and Mikkel Thorup.  Fast fencing.  In Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing (STOC 2018), pages 564–573, 2018.  doi:10.1145/3188745.3188878.
  * [2] Mikkel Abrahamsen, Panos Giannopoulos, Maarten Löffler, and Günter Rote.  Geometric multicut.  In Proceedings of the 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019), volume 132 of LIPIcs, pages 9:1–9:15. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019.  doi:10.4230/LIPIcs.ICALP.2019.9.
  * [3] Alok Aggarwal, Heather Booth, Joseph O’Rourke, Subhash Suri, and Chee K. Yap.  Finding minimal convex nested polygons.  Information and Computation, 83(1):98 – 110, 1989.  doi:10.1016/0890-5401(89)90049-7.
  * [4] Alok Aggarwal, Heather Booth, Joseph O’Rourke, Subhash Suri, and Chee-Keng Yap.  Finding minimal convex nested polygons.  Information and Computation, 83(1):98–110, 1989.  doi:10.1016/0890-5401(89)90049-7.
  * [5] Gautam Das.  Approximation schemes in computational geometry. PhD thesis, University of Wisconsin, Madison, 1991.
  * [6] Peter Eades and David Rappaport.  The complexity of computing minimum separating polygons.  Pattern Recognition Letters, 14(9):715–718, 1993.  doi:10.1016/0167-8655(93)90140-9.
  * [7] Jack Edmonds.  Paths, trees, and flowers.  Canadian Journal of Mathematics, 17:449–467, 1965.  doi:10.4153/CJM-1965-045-4.
  * [8] 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.  doi:10.1137/0132072.
  * [9] Subir Kumar Ghosh.  Computing the visibility polygon from a convex set and related problems.  Journal of Algorithms, 12(1):75–95, 1991.  doi:10.1016/0196-6774(91)90024-S.
  * [10] John Hershberger and Jack Snoeyink.  Computing minimum length paths of a given homotopy class.  Computational Geometry: Theory and Applications, 4:63–97, 1994\.  doi:10.1016/0925-7721(94)90010-8.
  * [11] Klaus Jansen and Haiko Müller.  The minimum broadcast time problem for several processor networks.  Theoretical Computer Science, 147(1-2):69–85, 1995.  doi:10.1016/0304-3975(94)00230-G.
  * [12] Joseph SB Mitchell and Subhash Suri.  Separation and approximation of polyhedral objects.  Computational Geometry: Theory and Applications, 5(2):95–114, 1995\.  doi:10.1016/0925-7721(95)00006-U.
  * [13] Cao An Wang.  Finding minimal nested polygons.  BIT Computer Science section, 31(2):230–236, 1991.  doi:10.1007/BF01931283.
  * [14] Cao An Wang and Edward P. F. Chan.  Finding the minimum visible vertex distance between two non-intersecting simple polygons.  In Proceedings of the Second Annual ACM SIGACT/SIGGRAPH Symposium on Computational Geometry, Yorktown Heights, NY, USA, June 2-4, 1986, pages 34–42. ACM, 1986.  doi:10.1145/10515.10519.

##  Appendix A Omitted proofs of Section 2

See 2.1

######  Proof A.1.

By Observation 2 the fence $F$ has at least $t-1$ straight-line segments
Assume $F$ has also exactly $t-1$ segments. Let
$\mathcal{S}_{1},\ldots,\mathcal{S}_{t}$ be the non-overlapping non-collinear
triples and $S_{1},\ldots,S_{3t}$ be the sets of the non-collinear triple in
the order in which $F$ crosses them as above. Since $F$ is a simple polygon
there exists a polygonal chain $C$ starting at some point in $S_{3t}$ and
ending at some point in $S_{1}$. By Observation 2 there are $t-1$ straight-
line segments which are completely contained in $]S_{1},S_{3t}[$ which implies
that $C$ must consist of segments that are also completely contained in
$]S_{1},S_{3t}[$.

Now, we charge every of the $t-1$ segments to the piece of $F$ that connects
for each $\mathcal{S}_{i}$ with $i=1,\ldots,t-1$ some point in $S_{i+1}$ with
some point in $S_{i+2}$. Since the triples are non-overlapping each such
connection also requires a distinct segment. Then, for the connection of
$S_{3t-1}$ and $S_{3t}$ we require at least one more segment. Let $s$ be the
segment charged to the connection of $S_{3t-4}$ to $S_{3t-3}$. If we could
extend this segment to also intersect $S_{3t}$ we would violate that
$\mathcal{S}_{t-1}$ and $\mathcal{S}_{t}$ are non-overlapping. Symmetrically
for the segment charged to $S_{2}$ and $S_{3}$. Consequently, we require at
least one more segment.

###  A.1 Omitted proofs of Section 2.1

See 2.3

######  Proof A.2.

To prove this lemma, we will first number the eight inner polygons of the
variable gadget $A_{1},\ldots,A_{8}$. Any fence inside the variable gadget can
include any combination of $k$ inner polygons. We will prove this lemma, by
enumerating for every $k\in\\{1,8\\}$ all possible (non-symmetric)
combinations of including these inner polygons; Note that technically a fence
is allowed to include non-consecutive inner polygons. Note that any fence has
to consist of at least 3 segments and clearly every inner polygon of
$\mathcal{G}(v)$ can be fenced alone with 3 segments. For any possible fence
including multiple inner polygons, we show the existence of a certain number
of non-overlapping non-collinear triples, which provide a lower bound on the
number of segments for such a fence. All triples and the resulting lower
bounds on the number of segments in fencings including all possible
combinations of 2 to 8 inner polygons are shown in Appendix B. Enumeration
shows that a fence $F$ including $k$ inner polygons, has the minimum amount of
segments, if and only if the indices of the contained inner polygons are
consecutive (assuming $A_{8}$ and $A_{1}$ to be consecutive). In particular,
such a fence including 2, 3, 4, 5, 6, 7 or 8 inner polygons, requires (and can
be realized with) 3, 6, 8, 11, 13, 16 and 18 segments, respectively.

First observe that there are exactly two minimum link fencings, which include
exactly two neighboring inner polygons in one fence, both consisting of 12
segments total, both are shown in Figures 4(b) and 4(c). We can therefore
exclude any fence including six or more inner polygons, since they clearly
require more segments by themselves, which immediately eliminates the
possibility of including 6 or more inner polygons in one fence. Any fence
including five inner polygons requires at least 11 segments and at least one
additional fence is needed, which increases the segment count to at least 14.
Any fence including four inner polygons requires at least 8 segments. If the
remaining four segments are fenced together, we require at least 16 segments.
If they include a group of three polygons, we require at least 14 segments. If
two remaining polygons are grouped, we require 11 segments, but at least one
more fence (14 segments in total) are needed and if all remaining polygons are
fenced alone, we need 20 segments in total.

Next if three segments are fenced together, we require 6 segments and have
five inner polygons left. We already know that no fence including four or more
segments can be part of a minimum link fencing. If three of the remaining five
polygons are grouped we arrive at a total of at least 12 segments, with at
least one more fence needed. If at most two polygons are grouped, we need at
least three more fences and arrive at a total of at least 15 segments.

Finally, polygons could be fenced individually. Clearly there must be an even
number of individually fenced polygons. If all eight polygons are fenced
alone, we reach at least 24 segments, for six inner polygons fenced alone we
get 18 segments, four individually fenced polygons lead to 12 with at least
one more fence needed. Two inner polygons being fenced alone require at least
6 segments, with at least three more fences needed for the six left over
polygons, which require at least 9 segments leading to a total of 15 segments.

Therefore only two minimum link fencings exist, which require exactly 12
segments, and they group two neighboring inner polygons pairwise. We call the
fencing, which groups inner polygons, which are both contained in a gray
triangle with a true spike $\mathcal{F}_{t}$ and the other $\mathcal{F}_{f}$.

###  A.2 Omitted proofs of Section 2.2

#### Omitted lemmas and proofs for one isolated wire

Figure 10: The highlighted areas show that $b$ and $c$, $c$ and $d$, and $d$
and $e$ form non-collinear triples.

######  Lemma A.3 ($\star$).

No fence in a minimum link fencing $\mathcal{F}$ of an isolated wire $W$ of
$\mathcal{G}(c)$ bypasses two or more consecutive inner polygons of $W$.

######  Proof A.4.

Let $B_{1},\ldots,B_{k}$ be the inner polygons of an isolated wire $W$,
$T_{1},\ldots,T_{k}$ the corresponding gray triangles, and $F\in\mathcal{F}$ a
fence that bypasses two or more consecutive inner polygons of $W$. Also,
throughout the proof, let $B_{i}$ and $B_{j}$ with $i<j$ be two inner polygons
that are contained in $F$ such that $B_{i+1},\ldots,B_{j-1}$ are bypassed by
$F$.

Assume that $i+1<j-1$, i.e., there are at least three consecutive inner
polygons bypassed by $F$. Let $B_{i+1},B_{i+2}$ and $B_{i+3}$ be three such
consecutive polygons. Now, we find one sequence of at least three non-
overlapping non-collinear triples by construction. Let $b$, $c$, $d$, and $e$
be four sets such that $b$ and $c$, $c$ and $d$, and $d$ and $e$ form such
triples. Compare Figure 10 for an illustration.

By Observation 2 $F$ contains at least two complete segments in $]b,e[$.
Moreover, $F$ has to cross the same triples in reverse order since it is a
simple polygons and contains both $B_{i}$ and $B_{j}$ for $j>i+3$.
Consequently, we find another two complete segments in $]e,b[$. We split $F$
at $b$ and $e$. This creates three fences $F_{1}$, $F_{2}$, and $F_{3}$ for
which it holds that $|F_{1}|+|F_{2}|+|F_{3}|=|F|+4$ One fence does not contain
any inner polygons and can be deleted, let $F_{2}$ be this fence. Sine $F_{2}$
was created by splitting along $b$ and $e$ it contained at least four complete
segments plus the two segments introduced in the splitting operation. Hence,
with $|F|+4=|F_{1}|+|F_{2}|+|F_{3}|\geq|F_{1}|+|F_{3}|+6$ it follows that
$|F|\geq|F_{1}|+|F_{3}|+2>|F_{1}|+|F_{3}|$. Since $F$ was part of a minimum
link fencing we may conclude that $F$ at most bypasses two consecutive inner
polygons.

Figure 11: We can locally shortcut any fence $F$ passing $a$ and $b$ in both
directions by connecting the two intersection points of $F$ with $a$ ($b$)

In the following let $B_{i+1}$ and $B_{i+2}$ be the two consecutive polygons
bypassed by $F$. Consequently, we know that $F$ contains $B_{i}$ and
$B_{i+3}$. Figure 11 illustrates the following cases.

Assume $F$ does not contain any other inner polygons, i.e., $F$ contains only
two inner polygons. In this case we find a sequence of four non-overlapping
non-collinear triples $a^{\prime}$ and $b$, $b$ and $c$, $c$ and $d$, $d$ and
$e^{\prime}$ which have to be crossed by $F$. Moreover, $F$ has to cross each
such triple in the reverse direction. Consequently, $F$ has crossed eight non-
overlapping non-collinear triples and consists by Lemma 2.1 of at least eight
segments. Replacing $F$ by two fences, both consisting only of triangles,
creates a fencing with less segments than $\mathcal{F}$. It remains to argue
the case that $F$ contains more than two inner polygons.

Let $F$ be such that there does not exist an inner polygon $B_{z}$ contained
in $F$ with $z>i+3$. Then there exists an inner polygon $B_{m}\in F$ and
$m<i$. Observe that there is a sequence of four non-overlapping non-collinear
triples $a^{\prime}$ and $b$, $b$ and $c$, $c$ and $d$, $d$ and $e^{\prime}$,
which is as in the case before and a sequence of four non-overlapping non-
collinear triples $e^{\prime}$ and $d$, $d$ and $c$, $c$ and $b$, and $b$ and
$a$ which is almost as before, with the difference that we use a set $a$ which
lies in $T_{i-1}$ and can be chosen as a segment which $F$ intersects twice.
By Observation 2 we find that $]a^{\prime},a[$ completely contains at least
seven segments of $F$.

We split $F$ at $a$, let $F_{m}$ and $F_{i}$ be the resulting fences such that
$F_{m}$ contains $B_{m}$ and $F_{i}$ contains $B_{i}$ and $B_{i+3}$. It holds
that $|F_{m}|+|F_{i}|=|F|+2$ and $|F_{i}|\geq 8$ since $F_{i}$ contains only
$B_{i}$ and $B_{i+3}$ and bypasses $B_{i+1}$ and $B_{i+2}$. Hence,
$|F|\geq|F_{m}|+6$ since $|F|+2=|F_{m}|+|F_{i}|\geq|F_{m}|+8$. Consequently,
replacing $F_{i}$ by two triangles only yields a fencing with the same number
of fences as $\mathcal{F}$. In the following assume that we delete $F_{i}$ and
introduce one triangular fence $F_{\Delta}$ that includes only $B_{i+3}$. The
goal is then to include $B_{i}$ into $F_{m}$ using at most three segments.

Consider $F_{m}$ and remove the segment introduced when splitting $F$ at $a$.
Let $p$ and $p^{\prime}$ be the two intersection points of $F$ with $a$ and
assume $p$ is closer to the base side of $T_{i-1}$. W.l.o.g. we assume that
neither $p$ nor $p^{\prime}$ are vertices of $F$. Let $c_{i}$ be the corner of
$T_{i-1}$ that would be disconnected from the component containing $a$ when
removing $T_{i}$ from the plane. If there exists a point $c$ in the component
containing $c_{i}$ such that the straight-line segments $pc$ and $p^{\prime}c$
both do not intersect $B_{i}$, are completely contained in $T_{i-1}$, and
their supporting lines leave $B_{i}$ in different half-planes, we just add
these two segments to $F_{m}$ which now contains also $B_{i}$.

Now assume such a point does not exist. By construction there exists a
straight-line segment starting at $p$, $p^{\prime}$ respectively, ends at the
boundary of $T_{i}$, and also intersects the boundary of $T_{i}$. Let $s$ be
such a segment for $p$ and $s^{\prime}$ one for $p^{\prime}$ and let $q$ and
$q^{\prime}$ be their endpoints on the boundary of $T_{i}$. Sine $p$ is closer
to the base of $T_{i-1}$ we may assume that the supporting line of $s$ leaves
$B_{i}$ to the right and the one of $s^{\prime}$ leaves $B_{i}$ to the left,
and $s$ and $s^{\prime}$ do not intersect. Connect the two endpoints of $s$
and $s^{\prime}$ with one segment along the boundary of $T_{i}$. This uses at
most three segments as required.

In preparation for the next case we are going to remove one additional
segment. Consider a set $a^{\prime\prime}$ that is intersected by $s$, such a
set is indicated in Figure 11. Since $F$ contained $B_{i}$ it had to contain
at least one point of $a^{\prime\prime}$ as well. Moreover, since $F$ was a
minimum link fence containing $B_{i}$111We are only aiming to contradict
minimality with respect to inclusion of polygons in the fence, for a given set
of polygons we may still assume that the initial fence was as short as
possible. we may assume that there is a vertex $v$ of $F$ that is now a vertex
of $F_{m}$ and there is a straight-line segment starting at $v$, intersecting
$a^{\prime\prime}$, intersecting the boundary of $T_{i}$ twice, and it lies in
$T_{i-1}$ and does not intersect $B_{i}$. Let $q^{\prime\prime}$ be the
endpoint of this segment. Replace the segments $vp$, $pq$, and $qq^{\prime}$
by $vq^{\prime\prime}$ and $qq^{\prime\prime}$. That is only two additional
segments.

Finally, assume that there exist inner polygons $B_{m},B_{l}\in F$ such that
$m<i$ and $l>i+3$. Split $F$ as above at $a$ and also at some set $e$ in
$T_{i+3}$. This leaves three fences $F_{m}$, $F_{l}$, and $F_{i}$. Similarly
to above $|F|+4=|F_{m}|+|F_{l}|+|F_{i}|\geq|F_{m}|+|F_{l}|+8$ from which we
derive $|F|\geq|F_{m}|+|F_{l}|+4$. By the above argumentation we can hence
replace $F$ by two fences $F_{m}$ and $F_{l}$ such that the new fencing has
the same number of segments. But now, observe that there is a sequence of non-
overlapping non-collinear triples which $F_{i}$ all has to cross, namely
$a^{\prime}$ and $b$, $b$ and $c$, $c$ and $d$, $d$ and $e$, $e^{\prime}$ and
$d$, $d$ and $c$, $c$ and $b$, and $b$ and $a$. By Observation 2 intervals
$]a^{\prime},e[$ and $]e^{\prime},a[$ completely contain three segments each.
Moreover, these sets can be chosen in such a way that the segments introduced
when splitting $F$ do only contain points of $a$ and $e$. See also Figure 11
for an illustration. Hence, $|F_{i}|\geq 10$ and consequently
$|F|\geq|F_{m}|+|F_{l}|+6$.

We now know that no fence of a minimum link fencing of an isolated wire
bypasses two or more consecutive inner polygons of that wire. However, it
might still bypass an unbounded number of polygons in total. Since there is a
sequence of four non-overlapping non-collinear triples for a fence that
includes $B_{i}$ and $B_{i+2}$ we obtain the following observation for a fence
bypassing at least one inner polygon.

Let $\mathcal{F}$ be a minimum link fencing of an isolated wire $W$ of
$\mathcal{G}(c)$, let $B_{1},\ldots,B_{k}$ be the inner polygons of $W$, and
$F\in\mathcal{F}$ a fence that bypasses $z>0$ inner polygons, then $F$
contains at least $4z+2$ segments.

While it is not possible anymore by Lemma A.3 to bypass multiple consecutive
polygons there could still be multiple fences in a minimum link fencing that
interleave and bypass many individual inner polygons.

######  Lemma A.5 ($\star$).

A minimum link fencing $\mathcal{F}$ of an isolated wire $W$ of
$\mathcal{G}(c)$ does not contain two distinct fences that interleave.

######  Proof A.6.

Let $B_{1},\ldots,B_{k}$ be the inner polygons of $W$ and assume that there
are fences $F,F^{\prime}\in\mathcal{F}$ of $W$ that interleave. By Lemma A.3
we know neither $F$ nor $F^{\prime}$ can bypass two or more consecutive inner
polygons. Consequently, there exist inner polygons $B_{i}$, $B_{i+1}$,
$B_{i+2}$, and $B_{i+3}$ such that w.l.o.g. $B_{i},B_{i+2}\in F$ and
$B_{i+1},B_{i+3}\in F^{\prime}$.

First, assume that $F$ and $F^{\prime}$ only contain these four polygons. By
Observation A.2 each fence bypassing one polygon contains at least six
segments. Hence, $|F|+|F^{\prime}|\geq 12$. By replacing $F$ and $F^{\prime}$
by two new fences, consisting of a triangle each, one containing $B_{i}$ and
$B_{i+1}$ and the other containing $B_{i+2}$ and $B_{i+3}$, we create a new
fencing with six segments less. A contradiction to $\mathcal{F}$ being a
minimum link fencing.

Now consider the case that $F$ and $F^{\prime}$ might contain more inner
polygons. First assume all further inner polygons of $F$ are before $B_{i}$
and all further inner polygons of $F^{\prime}$ are after $B_{i+3}$. Observe
that then $|F|+|F^{\prime}|\geq 14$ since we need to add at least one segment
to each fence. We split the fences $F$ and $F^{\prime}$ in the gray triangles
$T_{i-1}$, $T_{i+3}$ respectively. We first consider just $F$. After splitting
we now have two fences $F_{<i}$ and $F_{i}$. Let $F_{<i}$ be the fence
containing all inner polygons before $B_{i}$ and $F_{i}$ the fence containing
$B_{i}$ and $B_{i+2}$. By Observation A.2 we have $|F_{i}|\geq 6$.
Consequently $|F|=|F_{<i}|+|F_{i}|-2\geq|F_{<i}|+6-2=|F_{<i}|+4$ and hence
$|F_{<i}|\leq|F|-4$. Doing the same for $F^{\prime}$ we obtain
$F_{<i}^{\prime}$ and $F_{i}^{\prime}$. As before we can replace $F_{i}$ and
$F_{i}^{\prime}$ by two triangles $F_{\Delta}$ and $F_{\Delta}^{\prime}$. In
total the new fencing created like this has
$|F_{<i}|+|F_{\Delta}|+|F_{<i}^{\prime}|+|F_{\Delta}^{\prime}|\leq|F|+|F^{\prime}|-8+6=|F|+|F^{\prime}|-2$
segments.

Finally, $F$ and $F^{\prime}$ could contain polygons both before $B_{i}$ and
after $B_{i+3}$. By Lemma A.3 we know that then the fences repeatedly
interleave until at some inner polygon one fence stops. Let $m<l$ and w.l.o.g.
let $B_{m}$ be the last polygon included by $F$ and $B_{l}$ the first polygon
included by $F^{\prime}$ and assume that between $B_{l}$ and $B_{m}$ the two
fences interleave, i.e., $F$ includes $B_{m}$, $B_{m-2}$, etc. and
$F^{\prime}$ contains $B_{m-1}$, $B_{m-3}$ , etc.. Moreover, $F$ contains
$B_{l-1}$ and $F^{\prime}$ contains $B_{m+1}$ We can split $F$ and
$F^{\prime}$ as before in $T_{l-2}$ and $T_{m+2}$ using just four segments.
Let $F_{<m}$ and $F_{m}$ be the fences created from splitting $F$ such that
$F_{m}$ contains $B_{m},\ldots,B_{l-1}$ and $F_{<m}$ the remaining polygons
contained in $F$. Analogously for $F^{\prime}$ and $F_{<l}$ and $F_{l}$. Let
$M$ be the number of bypassed polygons for $F$ and $L$ the number of bypassed
polygons for $F^{\prime}$. We get that
$|F|+|F^{\prime}|=|F_{<m}|+|F_{m}|+|F_{<l}|+|F_{l}|-4$. We also know from
Observation A.2 that $|F_{m}|\geq 4M+2$ and $|F_{l}|\geq 4L+2$. Hence,
$|F|+|F^{\prime}|\geq|F_{<m}|+|F_{<l}|+4M+4L$ and hence
${\color[rgb]{0,0,0}|}F_{<m}{\color[rgb]{0,0,0}|}+{\color[rgb]{0,0,0}|}F_{<l}{\color[rgb]{0,0,0}|}\leq|F|+|F^{\prime}|-4M-4L$.
Finally, we can replace $F_{m}$ and $F_{l}$ by a series of triangular fences
that in sum have $3\cdot(M+L+2)/2$ which results in

$\displaystyle|F_{<m}|+|F_{<l}|+3/2(M+L+2)-4$
$\displaystyle\leq|F|+|F^{\prime}|-4M-4L+3/2(M+L+2)-4$
$\displaystyle=|F|+|F^{\prime}|-(5/2(M+L)+1).$

This concludes the proof as $\mathcal{F}$ cannot have been a minimum link
fencing for $W$.

Figure 12: All six non-collinear triples of a fence bypassing exactly one
inner polygon.

See 2.5

######  Proof A.7.

Let $B_{1},\ldots,B_{k}$ be the inner polygons of $W.$ Assume that $F$
bypasses an inner polygon $B_{j}$ for $2\leq j\leq k-1$. By Lemma A.3 we know
that $F$ never bypasses more than one consecutive inner polygon at a time.
Hence, we know that $B_{j-1}$ and $B_{j+1}$ are both contained in $F$. We
distinguish if $F$ bypasses $B_{j}$ above or below (both cases are shown in
Figure 13).

Assume $F$ bypasses $B_{j}$ above as shown in Figure 13 (a). Then we construct
a new fence including also $B_{j}$ as follows. Let $s_{1}$ and $s_{2}$ be two
segments such that $s_{1}$ lies inside the gray triangle $t_{i-1}$ of $W$ that
contains $B_{j-1}$ and $B_{j}$ and $s_{2}$ such that it lies inside the gray
triangle $t_{i}$ of $W$ containing $B_{j}$ and $B_{j+1}$. More specifically,
we choose $s_{1}$ such that its supporting line leaves $B_{j-1}$ and $B_{j}$
in one and $B_{j-2}$ in the other half-plane. Similarly, we chose $s_{2}$ such
that its supporting line leaves $B_{j}$ and $B_{j+1}$ in one and $B_{j+2}$ in
the other half-plane. The segments $s_{1}$ and $s_{2}$ can then be extended
such that they meet in a point that is inside the overlap of $t_{i-1}$ and
$t_{i}$ and below $B_{j}$. Moreover, they can be extended such that they
intersect any fence that contains $B_{j-1}$ and $B_{j+1}$ at least twice below
$B_{j-1}$ and $B_{j+1}$ respectively. See Figure 13(a) for an illustration.

Symmetrically we find two segments $s_{1}^{\prime}$ and $s_{2}^{\prime}$ whose
intersection point is above $B_{j}$ and whose supporting lines leave $B_{j-1}$
and $B_{j}$ in the same half-plane and $B_{j+1}$ in the other, $B_{j+1}$ and
$B_{j}$ in the same and $B_{j-1}$ in the other respectively. Again, these
segments can be extended to intersect $F$ twice, this time above $B_{j-1}$ and
$B_{j+1}$. See Figure 13(b) for an illustration.

As $F$ contains at least four segments inside $t_{i-1}$ and $t_{i}$ we can
replace those by $s_{1}$, $s_{2}$, $s_{1}^{\prime}$, and $s_{2}^{\prime}$
which yields a fence with at most equal number of links. Now, deleting the
single fence that fenced $B_{j}$ removes at least three links, a contradiction
to $\mathcal{F}$ being a minimum link fencing.

Figure 13: Rerouting of segments to include a bypassed inner polygon.

We can apply this procedure to all bypassed polygons. Since no fence can be
interleaving with $F$, we can simply remove all fences, which included any
polygon $B_{i}$ completely and still obtain a valid fencing, contradicting
that $\mathcal{F}$ is a minimum link fencing.

See 2.9

######  Proof A.8.

Let $B_{1},\ldots,B_{k}$ be the inner polygons of $W$. By Lemma 2.7 every
fence in $\mathcal{F}$ contains either one, two, or three consecutive inner
polygons. Let $f_{i}$ be the number of fences in $\mathcal{F}$ containing $i$
inner polygons. Then the number of segments of the fencing $\mathcal{F}$ can
be computed as $|\mathcal{F}|\geq 3f_{1}+3f_{2}+6f_{3}$ since for one or two
inner polygons we always can use one triangle and for three inner polygons we
have six segments by Lemma 2.6. Now, let $k_{i}$ be the number of segments in
a fence containing $i$ inner polygons. From this we get that $f_{i}=k_{i}/i$.
Substituting in the previous calculation we get $|\mathcal{F}|\geq
3k_{1}+3/2k_{2}+2k_{3}$. Hence, maximizing the number of inner polygons in
fences containing also two polygons minimizes the number of segments in the
fencing. Since $k$ is always even the minimum is attained at $3/2k$, i.e.,
when all inner polygons are part of a fence containing only two inner polygons
as claimed.

#### Omitted proofs for integrating the clause triangle

See 2.10

######  Proof A.9.

Assume there exists a fence $F$ that bypasses some polygons of
$\mathcal{G}(c)$. If $F$ only bypasses and contains polygons of one isolated
wire $W$ and is contained in the gray triangles of $W$ we can apply Lemma 2.5
contradicting the existence of $F$.

Next, assume that $F$ lies not only in the gray triangles of $W$ but still
only contains and bypasses inner polygons of $W$. This implies that $F$
contains $B_{1}$ of $W$ as else we could by construction find a fence that is
restricted to only the gray triangles of $W$. Let $T_{c}$ be the triangle
intersecting $T_{1}$ of $W$ and containing $B_{c}$. If $F$ was not restricted
to the $T=T_{c}\cup T_{1}\cup\ldots\cup T_{k}$ we could replace $F$ by a
congruent minimum link fence that is only contained $T$ by either splitting
$F$ if a whole segment is outside of $T$ or moving the one corner that lies
outside of $T$ which is always possible by construction. After that we can
again apply Lemma 2.5 by considering $T_{c}$ and $B_{c}$ part of the isolated
wire.

This means that $F$ has to include either $B_{c}$ or two inner polygons of
different wires if $F$ is to bypass any polygon of $\mathcal{G}(c)$. Now
assume $F$ was bypassing any inner polygon $B_{i}$ of some wire $W$ and $i>1$.
Let $F_{T}$ be $F$’s restriction to $T=T_{c}\cup T_{1}\cup\ldots\cup T_{k}$.
Add one temporary segment to $F_{T}$ to close the fence, this can always be
done in $T_{c}$. Now we can apply Lemma 2.5 to $F_{T}$. Each proof of one of
the lemmas leading to Lemma 2.5 implies a procedure of how to split $F_{T}$.
This results in two or more fences. Among those exists one that contains
$B_{j}$ with smallest $j$. Let $F_{T}^{j}$ be this fence. Either $F_{T}^{j}$
is such that it still contains the segment added initially to $F_{T}$ in which
case we just remove this segment and obtained a fencing with less segments or
$F_{T}^{j}$ does not contain this segment anymore. Recall, that every
procedure we implicitly defined saves at least two segments. Hence, adding the
segment we had added to $F_{T}$ to the remainder of $F-F_{T}$ still creates a
fencing with one segment less.

Consequently, we may assume that $F$ bypasses any combination of $B_{1}^{1}$,
$B_{1}^{2}$, $B_{1}^{3}$, or $B_{c}$. Without loss of generality we assume a
fence $F$ bypasses the first inner polygon $B_{1}^{1}$ of wire $W_{1}$. We can
again show that the amount of non-collinear triples between the lines $a$ and
$b$ is four, inducing at least four bends in this part of $F$.

Figure 14: The twelve sets.

We define twelve sets
$a,a^{\star},a^{\prime},a^{\prime\prime},b,b^{\star},b^{\prime},b^{\prime\prime},c,c^{\star},c^{\prime}$
and $c^{\prime\prime}$, as shown in Figure 14.Any fence crossing the following
pairs of sets contains a non-collinear triple starting at one set and ending
at the other:

  * •

$a$ and $b$

  * •

$a$ and $c$

  * •

$b$ and $c$

  * •

$a$ and $a^{\star}$

  * •

$a$ and $a^{\prime}$

  * •

$a^{\prime}$ and $a^{\prime\prime}$

  * •

$b$ and $b^{\star}$

  * •

$b$ and $b^{\prime}$

  * •

$b^{\prime}$ and $b^{\prime\prime}$

  * •

$c$ and $c^{\star}$

  * •

$c$ and $c^{\prime}$

  * •

$c^{\prime}$ and $c^{\prime\prime}$

Recall that $F$ is a fence bypassing $B_{1}^{1}$ hence $F$ has to include some
$B_{j}^{1}$ for $j>1$. More precisely, we may assume that $F$ contains
$B_{2}^{1}$ as else we could find a shorter fence by the above discussion. Let
$F^{\prime}$ be the fence that contains $B_{1}^{1}$. We make a case
distinction over which subset of
$\\{B_{c},B_{1}^{2},B_{2}^{1},B_{1}^{3},B_{2}^{3}\\}$ the fence $F^{\prime}$
contains as well.

Note that regardless of inclusion or exclusion of the clause triangle, any
fence crossing $a$ and $b$, $a$ and $c$ or $b$ and $c$ has one non-collinear
triple starting at one and ending at the other line segment. We therefore only
analyze the cases, which do not contain the clause triangle.

We analyze these cases one by one. In all cases we will turn $F$ and
$F^{\prime}$ into shorter fences $\hat{F}$, $\hat{F}_{1}^{\prime}$, and
$\hat{F}_{2}^{\prime}$ where $\hat{F}$ is going to be the fence including at
least $B_{1}^{1}$ and $B_{1}^{2}$ and is formed by just including $B_{1}^{1}$
instead of bypassing it. The fences $\hat{F}_{1}^{\prime}$ and
$\hat{F}_{2}^{\prime}$ containing the remaining triangles are going to be
formed by splitting $F^{\prime}$ at some point and removing the remaining
empty part. We call this _shortcutting_ $F^{\prime}$ at the segment where we
split it. Note that we can include $B_{1}^{1}$ into $\hat{F}$ at no additional
cost. This reduces the number of segments in $\mathcal{F}$ contradicting that
it is a minimum link fencing. To shorten the notation we write $[a,b,c]$ for a
sequence of non-collinear triple that $F$ has to cross.

#####  $\emptyset$:

If $B_{1}^{1}$ is contained in its own fence, we could instead reroute $F$
(Figure 15), and omit $F^{\prime}$ entirely, reducing the number of segments.

#####  $\\{B_{1}^{2}\\}$ and $F^{\prime}$ has to cross the sets
$[a^{\star},a,b,b^{\star},b,a,a^{\star}]$:

We can shortcut $F$ along $b$ for an additional cost of one segment, which
omits three segments, which are necessarily contained in the sequence
$[b,a,a^{\star},a,b]$.

#####  $\\{B_{2}^{2}\\}$ and $F^{\prime}$ has to cross the sets
$[a^{\star},a,b,b^{\prime},b^{\prime\prime},b^{\prime},b,a,a^{\star}]$:

This fence can be shortcut along $b^{\prime}$ for an additional cost of one
segment, which omits five segments, which are necessarily contained in the
sequence $b^{\prime},b,a,a^{\star},a,b,b^{\prime}$.

#####  $\\{B_{1}^{2},B_{2}^{2}\\}$ and $F^{\prime}$ has to cross the sets
$[a^{\star},a,b,b^{\prime},b^{\prime\prime},b^{\prime},b,a,a^{\star}]$:

This case can be resolved in the same way as $\\{B_{1}^{2}\\}$.

#####  $\\{B_{2}^{2},B_{2}^{3}\\}$ and $F^{\prime}$ has to cross the sets
$[a^{\star},a,b,b^{\prime},b^{\prime\prime},b^{\prime},b,c,c^{\prime},c^{\prime\prime},c^{\prime},c,a,a^{\star}]$:

This fence can be shortcut along $b^{\prime}$ and along $c^{\prime}$,
splitting it into two fences containing only inner polygons of the same wire.
This can be done at an additional cost of two segments saving five segments,
which are necessarily contained in the sequence
$b^{\prime},b,a,a^{\star},a,c,c^{\prime}$.

#####  $\\{B_{1}^{2},B_{2}^{2},B_{2}^{3}\\}$ and $F^{\prime}$ has to cross the
sets
$[a^{\star},a,b,b^{\prime},b^{\prime\prime},b^{\prime},b,c,c^{\prime},c^{\prime\prime},c^{\prime},c,a,a^{\star}]$:

This fence can be shortcut along $b$ and along $c^{\prime}$, splitting it into
two fences containing only inner polygons of the same wire. This can be done
at an additional cost of two segments saving four segments, which are
necessarily contained in the sequence $b,a,a^{\star},a,c,c^{\prime}$ and one
segment, necessarily contained in the sequence $c^{\prime},c,b$.

#####  $\\{B_{1}^{2},B_{2}^{2},B_{1}^{3},B_{2}^{3}\\}$ and $F^{\prime}$ has to
cross the sets
$[a^{\star},a,b,b^{\prime},b^{\prime\prime},b^{\prime},b,c,c^{\prime},c^{\prime\prime},c^{\prime},c,a,a^{\star}]$:

This fence can be shortcut along $b$ and along $c$, splitting it into two
fences containing only inner polygons of the same wire. This can be done at an
additional cost of two segments saving three segments, which are necessarily
contained in the sequence $b,a,a^{\star},a,c$.

#####  $\\{B_{1}^{2},B_{1}^{3}\\}$ and $F^{\prime}$ has to cross the sets
$[a^{\star},a,b,b^{\star},b,c,c^{\star},c,a,a^{\star}]$:

This case can be resolved in the same way as
$\\{B_{1}^{2},B_{2}^{2},B_{1}^{3},B_{2}^{3}\\}$.

#####  $\\{B_{1}^{2},B_{2}^{3}\\}$ and $F^{\prime}$ has to cross the sets
$[a^{\star},a,b,b^{\star},b,c,c^{\prime},c^{\prime\prime},c^{\prime},c,a,a^{\star}]$:

This case can be resolved in the same way as
$\\{B_{1}^{2},B_{2}^{2},B_{2}^{3}\\}$.

#####  $\\{B_{1}^{2},B_{2}^{2},B_{1}^{3}\\}$ and $F^{\prime}$ has to cross the
sets
$[a^{\star},a,b,b^{\prime},b^{\prime\prime},b^{\prime},b,c,c^{\star},c,a,a^{\star}]$:

This case can be resolved in the same way as
$\\{B_{1}^{2},B_{2}^{2},B_{1}^{3},B_{2}^{3}\\}$.

Figure 15: Non-collinear triples for any fence bypassing $B_{1}$

See 2.11

######  Proof A.10.

Figure 16: Non-collinear triples in a fence including at least (a) four or (b)
five inner polygons of a wire.

Assume there is a fence $F$, which includes inner polygons of two wires. By
Lemma 2.10, we know that all inner polygons of a wire included in $F$ are
consecutive in that wire. First also assume that $F$ contains $m>3$ inner
polygons of a single wire $W_{1}$. We split such a fence at a set $a$ in
$T^{1}_{1}$ (again using the sets marked in Figure 14) into two fences
$\hat{F}$ containing all $m$ inner polygons of the wire and $F_{o}$ and we
have $|\hat{F}|+|F_{o}|=|F|+2$. By Lemma 2.6, we know that $\hat{F}$ contains
at least $2m\geq 8$ segments. Assume $m$ to be odd, then we can replace
$\hat{F}$ with fences containing two consecutive polygons each (exactly
$\frac{m-3}{2}$), plus one containing three inner polygons, resulting in
$\frac{3m-9}{2}+6$ segments, which is smaller than $2m-2$ for any odd $m>5$,
yielding a better solution and contradicting $\mathcal{F}$ being a minimum
link fence. Assume $m$ to be even. Then by Lemma 2.9, we obtain $\frac{3m}{2}$
segments in total, which is smaller than $2m-3$ for any even $m>4$, again
yielding a better solution and contradicting $\mathcal{F}$ being a minimum
link fence.

It remains to analyze the cases $m=4$ and $m=5$. Assume $m=4$. We obtained
$F_{o}$ by shortcutting $F$ at $a$ and therefore $|F_{o}|=|F|+1$. Since there
are seven segments completely contained in the part of $F$ (the part of $F$
starting and ending at $a$, and being completely contained in $W_{1}$) which
is now omitted (using Observation 2), we can cover the four inner polygons of
$W_{1}$ with two triangles, using only six segments, which contradicts
$\mathcal{F}$ being a minimum link fence.

Assume now $m=5$. Since there are seven segments completely contained in the
part of $F$ which is now omitted (using Observation 2), we can cover the five
inner polygons of $W_{1}$ with two fences including three and two inner
polygons, respectively, i.e., $|\hat{F}_{1}|+|\hat{F}_{2}|=9$. Therefore we
can transform $F$ into a fence, which includes less than 4 inner polygons of
$W_{1}$ (in this case we turned it into $F_{o}$, which contains none), and it
suffices to analyze all cases, in which we contain at most the first one, two
or three inner polygons of any wire.

We again enumerate all cases, which are not symmetric to each other. We label
these cases with the included polygon of each wire with the highest index
(since no polygon of a wire is bypassed, this completely characterizes the
included inner polygons). Also, since we are only investigating non-symmetric
cases, we assume that the largest index of a polygon included in the first
wire is greater or equal to the one in the second one, which in turn is
greater or equal to the one in the third.

The possible cases are given below. For every case, we can give a tight lower
bound on the number of segments, which are at least needed, for any fence
including these inner polygons. This bound is achieved by analyzing non-
collinear triples of such a fence and by providing a fence which achieves this
bound. The complete enumeration is shown in Appendix C.

  * •

$\\{B_{1}^{3},B_{2}^{3},B_{3}^{3}\\}$

  * •

$\\{B_{1}^{3},B_{2}^{3},B_{3}^{2}\\}$

  * •

$\\{B_{1}^{3},B_{2}^{3},B_{3}^{1}\\}$

  * •

$\\{B_{1}^{3},B_{2}^{3}\\}$

  * •

$\\{B_{1}^{3},B_{2}^{2},B_{3}^{2}\\}$

  * •

$\\{B_{1}^{3},B_{2}^{2},B_{3}^{1}\\}$

  * •

$\\{B_{1}^{3},B_{2}^{2}\\}$

  * •

$\\{B_{1}^{3},B_{2}^{1},B_{3}^{1}\\}$

  * •

$\\{B_{1}^{3},B_{2}^{1}\\}$

  * •

$\\{B_{1}^{2},B_{2}^{2},B_{3}^{2}\\}$

  * •

$\\{B_{1}^{2},B_{2}^{2},B_{3}^{1}\\}$

  * •

$\\{B_{1}^{2},B_{2}^{2}\\}$

  * •

$\\{B_{1}^{2},B_{2}^{1},B_{3}^{1}\\}$

  * •

$\\{B_{1}^{2},B_{2}^{1}\\}$

  * •

$\\{B_{1}^{1},B_{2}^{1},B_{3}^{1}\\}$

  * •

$\\{B_{1}^{1},B_{2}^{1}\\}$

For the first twelve of these fourteen cases, we show how $F$ can be replaced
with a set of fences, which in sum contain less segments than $F$
contradicting that $\mathcal{F}$ is a minimum link fence; for details, we
refer again to Appendix C). All replacement fences (including and excluding
the clause triangle) are shown in Appendix C. The only exceptions are the two
cases $\\{B_{1}^{1},B_{2}^{1},B_{3}^{1}\\}$ and $\\{B_{1}^{1},B_{2}^{1}\\}$.
In both cases we can still replace $F$ as shown in Appendix C, however this
yields a fencing, which uses the same amount of segments as $F$. Note that
both fencings only contain fences, which are completely contained in
$T=T_{c}\cup T_{1}\cup\ldots\cup T_{k}$ (reusing the notation of the proof of
Lemma 2.10). The replacements for both cases contain at least one fence, which
includes only the first polygon of a wire. We will show that this implies that
we can replace all fences in that wire with a different set of fences, which
uses a smaller number of segments and thereby again contradicting that
$\mathcal{F}$ is a minimum link fencing.

Let $F_{1}$ be a fence in a wire including only the first polygon of that
wire. Since every wire contains an even number of inner polygons and no fence
includes four or more inner polygons by Lemma 2.7, we know that this wire has
to contain at least one other fence of size one or three. Let
$F_{2}\not=F_{1}$ be a fence in the wire, s.t., $B_{j}$ is the inner polygon
with the smallest index contained in $F_{2}$ and no other polygon $B_{k}$ with
$1<k<j$ is contained in a fence of size one or three. Therefore there are an
even number of inner polygons between $F_{1}$ and $F_{2}$. In particular if
$F_{2}$ contains three inner polygons, we can create new fences, s.t.,
$B_{2},B_{3},B_{4}$ are contained in one fence of size three and
$B_{5},\ldots,B_{k+2}$ are contained in $\frac{k-2}{2}$ fences of size two.
$F_{1}$ and $F_{2}$ require nine segments in total, while we can replace them
with two fences including $B_{1},B_{2}$ and $B_{3},B_{4}$, respectively,
requiring only six segments. If $F_{2}$ contains one inner polygon, we can
create new fences, s.t., $B_{2}$ is contained in one fence of size one and
$B_{3},\ldots,B_{k}$ are contained in $\frac{k-2}{2}$ fences of size two.
$F_{1}$ and $F_{2}$ require six segments in total, while we can replace them
with one fence including $B_{1},B_{2}$, requiring only three segments.

#### Omitted proofs for interaction with the variable gadgets

See 2.13

######  Proof A.11.

Note that inclusion of the last polygon of a wire into a fence of a variable
gadget always incurs an additional cost (of two or three, depending on the
state of the gadget). The only reason a minimum link fencing would choose to
do so is the fact that, such an inclusion reduces the number of inner
polygons, which have to be fenced in a wire from the even number $k$ down to
the uneven number $k-1$, which in turn allows the wire to treat the clause
triangle as its first inner polygon, and we save the three segments of the
clause triangle, leading to a cost of $\frac{3(k_{a}+k_{b}+k_{c})}{2}$ and the
variable gadget segment number increases from $12$ to $14$.

Note further that a minimum link fencing would never choose to do so for two
or three wires, since the benefit of including the clause triangle in a fence
of a wire can only be achieved once. Assume that there is a second wire in the
satisfying state, which add a further charge of (at least) two additional
segments at its variable gadget. By Lemma 2.11, we know that the clause
triangle is only included in a fence of one of the two wires. The second wire
has to fence an odd number of inner polygons and therefore has to include
either a fence of size one or three. It therefore still requires
$\frac{3k}{2}$ segments. Therefore only one wire will ever be put in the
satisfying state, even if two or all three variables would allow their
connected wires to be put in the satisfying state for an additional charge of
two segments each.

#### Full correctness proof

See 2.14

######  Proof A.12.

Given an instance of planar $3,4$-, we create and place a variable gadget
$\mathcal{G}(v)$ for every variable $v\in\mathcal{V}$ and a clause gadget
$\mathcal{G}(c)$ for every clause $c$, as described above. The wires of
$\mathcal{G}(c)$ connect to a true spike of $\mathcal{G}(v)$ if $v$ appears as
a positive literal and to a negative spike if $v$ appears as a negative
literal in $c$.

Assume we are given a satisfying variable assignment for the instance of
planar $3,4$-. By Lemma 2.13 in order to be able to find a fencing with
$\frac{3(k_{a}+k_{b}+k_{c})}{2}$ segments for every clause gadget, at least
one wire must be in the satisfying state. If one wire is in the satisfying
state we can include the last inner polygon of the wire for an additional two
segments if and only if the corresponding variable gadget is in the proper
state (Lemma 2.12). Since every clause has one variable, which satisfies this
clause, we choose this variable gadget to be in this state, and fence the
variable gadget accordingly, leading to twelve segments plus two segments, per
clause, which is connected via a wire in the satisfying state to it. Since in
the variable assignment, every clause has such a literal and every variable is
either true or false, we can do this for every clause and are never required
to put a variable gadget both in its true and its false state. The final cost
is $|\mathcal{V}|\cdot
12+\sum\limits_{c\in\mathcal{C}}(\frac{3(k^{c})}{2}+2)$, where $k^{c}$ is the
number of inner polygons of all three wires of $\mathcal{G}(c)$ summed up.

Now assume that we are given a fencing of the created BMLF instance with
exactly $|\mathcal{V}|\cdot
12+\sum\limits_{c\in\mathcal{C}}(\frac{3(k^{c})}{2}+2)$ segments. This implies
that for every clause gadget, there is one wire gadget in the satisfying
state. We follow this wire up to the variable gadget, which has to be in the
true state if the wire is connected to a true spike and in a false state
otherwise. We set the corresponding variable of the variable gadget to true in
the former and to false in the latter case. Therefore every clause has one
variable, which satisfies the clause. Since no fencing of a variable gadget
exists, in which both a wire connected to a true spike and a wire connected to
a false spike can be put into the satisfying state (Lemma 2.12), the implied
variable assignment is consistent. Finally, this might not necessarily assign
all variables to a fixed truth assignment, since even if a clause might be
satisfiable with two or even all three literals, we will never set more than
one wire into the satisfying state. All variables, which do not have a truth
value assigned yet, can safely be assigned a random value (e.g., true or false
if their variable gadget is true or false).

We conclude that the instance of planar $3,4$\- is satisfiable if and only if
the constructed two-colored BMLF instance admits a fencing with exactly
$|\mathcal{V}|\cdot 12+\sum\limits_{c\in\mathcal{C}}(\frac{3(k^{c})}{2}+2)$
segments.

##  Appendix B Complete enumeration of possible fences in a variable gadget

This section contains the complete enumeration of all possible cases, which
are considered in teh proof of Lemma 2.3. In particular, we enumerate all
possibilities of which $k$ inner polygons could be included in a single fence,
but compensate for rotational and axial symmetry, i.e., two groupings are
considered rotationally symmetric if we can construct one from the other, by a
combination of shifting all indices of included polygons by the same constant
(recall that all computations are considered modulo 8, and we write the index
0 and 8 interchangeably) and relabeling all indices $i$ as $8-i$ (mirroring
the instance at a straight line).

Clearly there is exactly one possibility for fencing 0, 1, 7 or 8 inner
polygons. Moreover, the number of choosing $k$ polygons to fence is also
characterizing how to chose $8-k$ polygons (which are not fenced) and
therefore the number of cases is symmetric for 2 and 6, and 3 and 5. It
remains to compute the correct number of cases for 2, 3 and 4.

Exclusively accounting for rotational symmetry, we can compute the number
$f^{r}(k)$ with the formula

$f^{r}(k)=\frac{1}{8}\cdot\sum\limits_{d|\text{gcd}(k,8-k)}\phi(d){{8/d}\choose{k/d}}$

where $\phi$ is Eulers $\phi$-function, i.e., the number of co-prime integers
smaller than $k$ including 1. Using this formula we obtain four cases for two
polygons (non of which are symmetric to each other), seven cases for three
polygons (two of which can be eliminated due to the additional axial symmetry)
and ten cases for four polygons (three of which are symmetric).

All cases are shown below in two individual figures, once illustrating the
lower bound (the black numbers) on the left, using non-overlapping, non-
colinear triples and once showing that this bound is in fact tight, by
providing a fence achieving this exact number of segments (shown in blue).

Figure 17: Fences including 2 polygons Figure 18: Fences including 3 polygons
Figure 19: Fences including 4 polygons Figure 20: Fences including 5 polygons
Figure 21: Fences including 6 polygons Figure 22: Fences including 7 polygons
Figure 23: Fences including 8 polygons

##  Appendix C Complete enumeration of possible fences at the clause triangle

This section illustrates the enumeration argument of the proof of Lemma 2.11.
Every case is shown four times in a column. The first row shows the lower
bound on the number of segments for any fence including all polygons of this
case, indicated by the three numbers in the upper left corner. These labels
should be read as XYZ corresponding to the case
$\\{B_{X}^{1},B_{Y}^{2},B_{Z}^{3}\\}$. The second row shows that all given
bounds are in fact tight, as they can be achieved with the shown blue fences.
The third and fourth row show (except for cases 111 and 110), that such a
fence can be replaced with a collection fences, which in total achieve a lower
number of segments, while either including (3rd row in green) or excluding
(4th row in red) the clause triangle, i.e., in both cases, the original fence
was not minimal.

Figure 24: Fences including exactly 3 inner polygons of one and at most 3 of
any other wire. Figure 25: Fences including exactly 3 inner polygons of one
and at most 3 of any other wire. Figure 26: Fences including exactly 3 inner
polygons of one and at most 3 of any other wire. Figure 27: Fences including
exactly 2 inner polygons of one and at most 2 of any other wire. Figure 28:
Fences including exactly 2 inner polygons of one and at most 2 of any other
wire. Figure 29: Fences including exactly 1 inner polygons of one and at most
1 of any other wire.

##  Appendix D Omitted Proofs of Section 3

See 3.2

######  Proof D.1.

Let $\mathcal{H}^{\cap}\subseteq\mathcal{H}$ be the set of holes, which
intersect the joint convex hull $C$ of $T_{1}$ and $T_{2}$ or are fully
contained in it. Let $l$ be a splitting segment with endpoints $p\in T_{1}$
and $q\in T_{2}$. Observe, that since $l$ is completely contained in
$C-\mathcal{H}$ we, by definition of equivalent splitting segments, can
disregard any hole $H\not\in\mathcal{H}^{\cap}$.

Let $l\in C$ be a splitting segment of $T_{1}$ and $T_{2}$, which has a set
$L\subseteq\mathcal{H}^{\cap}$ of holes to its left and a set
$R\subseteq\mathcal{H}^{\cap}$ to its right. There exists another splitting
segment $l_{c}$ whose supporting line is a bitangent on two holes, say
$H_{L}\in L$ and $H_{R}\in R$, such that $l_{c}$ has also $L$ to its left and
$R$ to its right. We obtain the splitting segment $l_{c}$ from $l$ by rotating
$l$ first around its center point until it touches either $H_{L}$ or $H_{R}$
in a point $r$ and then continue to rotate $l$ around $r$ until it touches the
second hole, see Figure 8(a). Since any pair of holes has at most four
bitangents (Figure 8(b)) there are at most $4|\mathcal{H}^{\cap}|^{2}$
equivalence classes.

See 3.4

######  Proof D.2.

Throughout, we consider the triangulation $\mathcal{T}$ of the free space of
$\mathcal{P}$. Let $t+1$ be the number of colors in the given instance and
$c_{1},\ldots,c_{t}$ be the colors of polygons in $\mathcal{P}$ with
$c_{i}\neq f(Q)$ for all $i=1,\ldots,t$.

Observe that the homotopy of a fence including exactly one polygon
$P\in\mathcal{P}$ is unique. We find a path $\alpha$ with this homotopy in the
triangulated free space between the polygons in $\mathcal{P}$ by traversing
the boundary of $P$ clockwise and at every corner of the polygon adding every
incident triangle of $\mathcal{T}$ in clockwise order to a list. This yields a
series of triangles from which we can construct a loop $\alpha$ such that $P$
is contained in $\alpha$. This can be done, for example, by connecting all
midpoints of triangulation segments of a triangle and its successor in the
loop. Then, we use Theorem 3.1 to obtain a minimum-link fence for $P$ from
$\alpha$ or determine that no fence with at most $k$ links exists. Computing
all individual fences requires $O(|\mathcal{P}|kn)=O(kn^{2})$ time.

Next, we consider every pair $P_{1},P_{2}\in\mathcal{P}$ with $P_{1}\neq
P_{2}$, $c_{i}=f(P_{1})=f(P_{2})$ and $i\in\\{1,\ldots,t\\}$. Note that in
contrast to a fence containing only one polygon, a fence containing exactly
two polygons can belong to several different homotopy-classes w.r.t. the
remaining polygons.

Now, we describe how to compute a minimum-link fence $F$ for two polygons
$P_{1}$ and $P_{2}$ of $\mathcal{P}$. Recall that all polygons in
$\mathcal{P}$ together have $n$ corners. Since we have only $O(n)$ triangles
in $\mathcal{T}$ we can iterate over all possible $O({n\choose k})\in
O(n^{k})$ ordered tuples of $k$ triangles. Fix in the following such an
ordered $k$-tuple $(T_{1},\ldots,T_{k})$ of triangles in $\mathcal{T}$. There
are only $O(|\mathcal{P}|^{2})$ many non-equivalent splitting segments
connecting points in triangles $T_{i}$ and $T_{i+1}$ by Lemma 3.2.
Consequently, we can iterate over the $O((|\mathcal{P}|^{2})^{k})=O(n^{2k})$
many different combinations of splitting segments between consecutive
triangles. In case there are two consecutive triangles between which no
possible splitting line exists we reject this tuple of triangles. Assume in
the following that we fix for every pair $T_{i}$ and $T_{i+1}$ a splitting
segment $l_{i}$.

It remains to construct a plane loop $\alpha$ as input for the algorithm of
Hershberger and Snoeyink [10] or decide that no such loop exists for the fixed
choices of triangles and splitting segments. From the triangles
$T_{1},\ldots,T_{k}$ and the splitting segments $l_{1},\ldots,l_{k}$ we derive
a sequence of triangles $\tau_{1},\ldots,\tau_{z}$ of $\mathcal{T}$ that
$\alpha$ has to visit. Since the triangulation $\mathcal{T}$ is defined by the
corners of polygons in $\mathcal{P}$ each splitting segment $l_{i}$ gives rise
to a unique sequence of triangles. We concatenate all these sequences starting
with the sequence induced by $l_{1}$ to obtain the sequence
$\Theta=(\tau_{1},\ldots,\tau_{z})$. Observe, that triangles along this
sequence may repeat and that $\tau_{1}=\tau_{z}$.

It remains to decide if there exists a plane loop $\alpha$ visiting each
triangle of $\Theta$ in order. To make the following description simpler let
$s_{i}$ be the shared boundary of $\tau_{i}$ and $\tau_{i+1}$. If for no $i$
with $i\in\\{1,\ldots,z-1\\}$, we find that $s_{i}=s_{i+1}$ we create a loop
$\alpha$ by connecting the centerpoint of $s_{i}$ with the one of $s_{i+1}$.
Since no boundary repeats, this is always possible without any centerpoint and
hence triangle being used twice. Finally, we add the segment from the
centerpoint of $s_{z}$ to the centerpoint of $s_{1}$ which is also always
possible as $\tau_{1}=\tau_{z}$.

Now assume there exist at least two indices $i$ and $j$ with $i\neq j$ and
$i,j\in\\{1,\ldots,z\\}$ such that $s_{i}=s_{j}$. Build the loop as before and
let $\alpha_{1},\ldots,\alpha_{z}$ be the segments in the constructed loop.
Since we allow repeated boundaries there exist subsequences among the
$\alpha_{1},\ldots,\alpha_{z}$ that are repeated. In the following we assume
that we only consider inclusion maximal repeated subsequences. Let
$A=\\{\alpha_{1}^{\prime},\ldots,\alpha_{a}^{\prime}\\}$ be one occurrence of
such a subsequence of the $\alpha_{i}$’s that is repeated at least once and
let $\hat{A}$ be a different occurrence. Let
$s_{1}^{\prime},\ldots,s_{a}^{\prime}$ be the subsequence of the $s_{i}$’s
that correspond to the triangle boundaries passed by the segments in $A$ and
$\hat{A}=\\{\hat{\alpha_{1}},\ldots,\hat{\alpha_{a}}\\}$. Now observe that in
a plane loop the vertices of $A$ and $\hat{A}$ have to always appear in the
same order along $s_{1}^{\prime},\ldots,s_{a}^{\prime}$. If they would not,
let $s_{i}^{\prime}$ and $s_{i+1}^{\prime}$ for $i\in\\{1,\ldots,a-1\\}$ be
two segments such that the vertices of $A$ and $\hat{A}$ on $s_{i}^{\prime}$
and $s_{i+1}^{\prime}$ are not in the same order. Without loss of generality
assume the vertex of $A$ on $s_{i}^{\prime}$ is above the one of $\hat{A}$ and
the opposite is true for $s_{i+1}^{\prime}$, then we find that $\alpha_{i}$
and $\hat{\alpha_{i}}$ cross. Hence, the only decision to make is to decide,
for each pair of repeated subsequences, in which order their vertices appear
along the corresponding triangle-boundaries. Since every repeated subsequence
implies an intersection between two segments $l_{i}$ and $l_{j}$ with $i\neq
j$ and $i,j\in\\{1,\ldots,k\\}$ we find that there are at most $k^{2}$ such
repeated sequences. Consequently, there are at most $2^{O(k)}$ possible ways
to distribute the center points in each shared part along the boundaries.

To sum up, for one pair of polygons $P_{1},P_{2}$ we have to consider
$O(n^{2k})$ possible non-homotopy equivalent fences and for each homotopy we
can check in $O(n^{2}\cdot 2^{k})$ if there exists a plane loop $\alpha$
realizing it, leading to a total runtime of $O(2^{k}\cdot n^{2k+2})$ to
enumerate every potential homotopy of a minimum link fence. For each of the
$O(n^{2k})$ different homotopies, we can use Theorem 3.1 to compute a minimum
link fence in $O(kn)$, hence we can compute a minimum link fences for all
pairs of polygons in $O(n^{2}\cdot kn^{2k+2})=O(kn^{2k+4})$.

If for any polygon no fence, alone or in a pair with another polygon, with $k$
or fewer links is found, we return that no solution exists. Otherwise, let
$\lambda_{uv}$ be the number of links for a minimum link fence containing
$P_{u},P_{v}\in\mathcal{P}$ and $\lambda_{u}$ the number of links for a
minimum link fence containing only $P_{u}\in\mathcal{P}$. Consider a complete
graph $G$ containing one vertex $u$ for each polygon $P_{u}\in\mathcal{P}$ and
one more vertex $x$ if $|\mathcal{P}|$ is odd. Set the edge-weights
$w(u,v)=\min\\{\lambda_{uv},\lambda_{u}+\lambda_{v}\\}$ and
$w(x,u)=\lambda_{u}$ for $P_{u},P_{v}\in\mathcal{P}$. If for some
$P_{u}\in\mathcal{P}$ or pair $P_{u},P_{v}\in\mathcal{P}$ no fence with $\leq
k$ segments existed we remove that edge.

To find a minimum-link fencing of $\mathcal{P}$ it now suffices to compute a
minimum weight perfect matching in $G$. Let $M$ be such a matching. Then, a
minimum link fencing $\mathcal{F}$ of $\mathcal{P}$ can be constructed from
$M$ in the following way. If $uv\in M$, we add the (pre-computed) minimum link
fences containing only $P_{u}$ and $P_{v}$ to $\mathcal{F}$ if the weight
$w(u,v)=\lambda_{u}+\lambda_{v}$ or the fence containing $P_{u}$ and $P_{v}$
if $w(u,v)=\lambda_{uv}$. If $|\mathcal{P}|$ was odd we also find an edge
$xu\in M$ and we add the fence containing only $P_{u}$ to the fencing.

Finding a minimum weight perfect matching in a general graph with $V$ vertices
and $E$ edges can be done for example in $O(V^{2}E)$ time via finding a
maximum weight perfect matching (e.g. [7]) in the same graph with edge weights
set to maximum edge-weight plus one minus the original edge-weight. Since $G$
has $O(|\mathcal{P}|)$ vertices and $O(|\mathcal{P}|^{2})$ edges we can
compute this matching in $O(|\mathcal{P}|^{4})=O(n^{4})$, which is dominated
by the initial computation of the minimum link fences.