# Covering Polygons is Even Harder

Mikkel Abrahamsen111Basic Algorithms Research Copenhagen (BARC), University of
Copenhagen. BARC is supported by the VILLUM Foundation grant 16582.

(June 4, 2021)

###### Abstract

In the Minimum Convex Cover (MCC) problem, we are given a simple polygon
$\mathcal{P}$ and an integer $k$, and the question is if there exist $k$
convex polygons whose union is $\mathcal{P}$. It is known that MCC is
$\mathsf{NP}$-hard [Culberson & Reckhow: Covering polygons is hard, FOCS
1988/Journal of Algorithms 1994] and in $\exists\mathbb{R}$ [O’Rourke: The
complexity of computing minimum convex covers for polygons, Allerton 1982]. We
prove that MCC is $\exists\mathbb{R}$-hard, and the problem is thus
$\exists\mathbb{R}$-complete. In other words, the problem is equivalent to
deciding whether a system of polynomial equations and inequalities with
integer coefficients has a real solution.

If a cover for our constructed polygon exists, then so does a cover consisting
entirely of triangles. As a byproduct, we therefore also establish that it is
$\exists\mathbb{R}$-complete to decide whether $k$ triangles cover a given
polygon.

The issue that it was not known if finding a minimum cover is in $\mathsf{NP}$
has repeatedly been raised in the literature, and it was mentioned as a “long-
standing open question” already in 2001 [Eidenbenz & Widmayer: An
approximation algorithm for minimum convex cover with logarithmic performance
guarantee, ESA 2001/SIAM Journal on Computing 2003]. We prove that assuming
the widespread belief that $\mathsf{NP}\neq\exists\mathbb{R}$, the problem is
not in $\mathsf{NP}$.

An implication of the result is that many natural approaches to finding small
covers are bound to give suboptimal solutions in some cases, since irrational
coordinates of arbitrarily high algebraic degree can be needed for the corners
of the pieces in an optimal solution.

> There is no point in studying a mathematical model unless it helps to solve
> certain practical problems.
>
> — Theodosios Pavlidis [41]

> It is certainly counterproductive to dismiss complicated theoretical methods
> solely on the grounds of impracticality.
>
> — Bernard Chazelle [13]

##  1 Introduction

Polygons are among the geometric structures that are most frequently used to
model physical objects, as they are suitable for representing a wide variety
of shapes and figures in computer graphics and vision, pattern recognition,
robotics, computer-aided design and manufacturing, and other computational
fields. Polygons may have very complicated shapes that make it difficult to
find algorithms to process them directly. A natural first step in designing
algorithms is to decompose the given polygon $\mathcal{P}$ into more basic
_pieces_ of a restricted type that permits very efficient processing. Here,
the union of the pieces must be exactly the given polygon $\mathcal{P}$. When
such a decomposition has been obtained, the partial solutions to the
individual pieces can be combined to obtain a solution for the complete
polygon $\mathcal{P}$. By “more basic pieces,” we mean pieces that belong to a
more restricted class of polygons. Ideally, we find a decomposition of the
polygon $\mathcal{P}$ into the minimum number of pieces.

Many different decomposition problems arise this way, depending on
restrictions on the polygon $\mathcal{P}$, the type of basic pieces, and
whether the decomposition is a cover or a partition. In covering problems, we
just require the union of the pieces to equal $\mathcal{P}$, whereas in
partition problems, we have the further requirement that the pieces be
interior-disjoint. Another important distinction is whether or not _Steiner
points_ are allowed. A Steiner point is a corner of a piece in a decomposition
which is not also a corner of $\mathcal{P}$. Furthermore, it often makes a big
difference whether or not $\mathcal{P}$ is allowed to have holes.

Because of the many variants of decomposition problems, their applicability
within many practical domains, and the very appealing fundamental nature and
the creativity and technical skills required to solve them, numerous papers
have been written about these problems. The vast literature is documented in
several highly-cited books and survey papers that give an overview of the
state-of-the-art at the time of publication [13, 29, 49, 15, 28, 35, 38].

One of the first decomposition problems to be studied was that of covering a
polygon with convex polygons. Pavlidis studied this problem from a practical
angle in relation to shape analysis and pattern recognition in a series of
papers and a book, the first paper from 1968 [40, 43, 41, 23, 42, 39]; see
Figure 1 (left). The related $\mathsf{NP}$-complete problem of covering an
orthogonal polygon with a given number of rectangles was mentioned by Garey
and Johnson’s famous book [24, p. 232], who denoted the problem Rectilinear
Picture Compression, since a collection of pixels can be compactly represented
as their minimum rectangle cover. For more recent practical work involving
versions of convex covering problems, see the surveys [45, 53] and the paper
[5].

Figure 1: Left: Two polygons (an E and a Chinese character for ‘pig’) with
convex covers drawn on top, from the paper [39]. Right: A polygon where the
minimum cover has a piece not bounded by edge extensions and needing Steiner
points, from the paper [36].

O’Rourke and Supowit [37] proved that for polygons with holes, it is
$\mathsf{NP}$-hard to find minimum covers using convex, star-shaped, and
spiral polygons as pieces. This was established with and without Steiner
points allowed. When Steiner points are not allowed, the covering problems are
clearly in $\mathsf{NP}$ and are thus $\mathsf{NP}$-complete, whereas the ones
with Steiner points allowed are not immediately seen to be decidable at all.
In the paper [36], O’Rourke proved the convex covering problem with Steiner
points to be decidable by showing that any given instance can be expressed as
a Tarski formula. In modern terms, we can say that he proved
$\exists\mathbb{R}$-membership. He gave the example shown in Figure 1 (right)
of a polygon $\mathcal{P}$ where Steiner points are needed and edge extensions
of $\mathcal{P}$ are not sufficient to form the pieces of a minimum cover. The
figure is now the logo of The Society of Computational Geometry and often also
of Symposium on Computational Geometry.

Since the $\mathsf{NP}$-hardness reductions in [37] relied on polygons with
holes, it was still not known if the covering problems for polygons without
holes could be solved efficiently. Chazelle and Dobkin [14] showed already in
1979 that a polygon without holes can be _partitioned_ into a minimum number
of convex pieces in polynomial time; a problem that had also been believed to
be $\mathsf{NP}$-hard, so this might have given hope for the covering problems
as well. However, it was soon proved that some covering problems are
$\mathsf{NP}$-hard even for polygons without holes. The first one was
apparently the problem of covering a polygon with a minimum number of star-
shaped polygons, which is usually known as the Art Gallery problem. The first
proof is often attributed to Alok Aggarwal’s PhD thesis [4] (see for instance
[17]), which is unfortunately practically unavailable. The first published
proof appears to be in a paper by Lee and Lin [30]. Then followed the proof by
Culberson and Reckhow [17] that it is likewise $\mathsf{NP}$-hard to cover
polygons without holes with a minimum number of convex pieces. The authors
added the comment: _“We are unable to show that general convex covering is in
$\mathsf{NP}$”_. The issue that the problem is not known to be in
$\mathsf{NP}$ has been raised in many other papers and books [36, 26, 20, 49,
16, 35, 28, 29], and was mentioned as a “long-standing open question” already
in 2001 [20]. Christ [16] proved that deciding if a polygon can be covered by
a minimum number of _triangles_ is also $\mathsf{NP}$-hard.

In this paper, we prove that it is $\exists\mathbb{R}$-complete to decide if a
polygon can be covered by a given number of convex pieces. The problem is thus
not in $\mathsf{NP}$, assuming the widespread belief that
$\mathsf{NP}\neq\exists\mathbb{R}$. Our reduction uses techniques that were
developed for proving that Art Gallery and some versions of geometric packing
are $\exists\mathbb{R}$-complete [2, 3]. As a biproduct, we show that it is
even $\exists\mathbb{R}$-complete to find a minimum triangle cover. The
hardness holds also when the corners of $\mathcal{P}$ are in general position,
i.e., no three are collinear.

###  1.1 Existential theory of the reals

In order to define the complexity class $\exists\mathbb{R}$, we first define
the problem Etr in the style of Garey and Johnson [24].

Instance: A well-formed formula $\Phi(x_{1},x_{2},\ldots,x_{n})$ using symbols
from the set

$\left\\{x_{1},x_{2},\ldots,x_{n},\land,\lor,\lnot,0,1,+,-,\cdot,\allowbreak\
(\ ,\ )\ ,=,<,\leq\right\\}.$

Question: Is the expression

$\exists
x_{1},x_{2},\ldots,x_{n}\in\mathbb{R}\colon\Phi(x_{1},x_{2},\ldots,x_{n})$

true?

The complexity class $\exists\mathbb{R}$ consists of all problems that are
many-one reducible to Etr in polynomial time, and a problem is
$\exists\mathbb{R}$-hard if there is a reduction in the other direction. It is
currently known that

$\mathsf{NP}\subseteq\exists\mathbb{R}\subseteq\mathsf{PSPACE}.$

It is not hard see that the problem Etr is $\mathsf{NP}$-hard, yielding the
first inclusion. The containment $\exists\mathbb{R}\subseteq\mathsf{PSPACE}$
is highly non-trivial, and it was first established by Canny [9].

As examples of $\exists\mathbb{R}$-complete problems, we mention problems
related to realization of order-types [44, 34, 52], graph drawing [8, 19, 31],
recognition of geometric graphs [11, 12, 27, 33], straightening of curves
[21], guarding polygons [2], Nash-equilibria [7, 25], linkages [1, 47, 48],
matrix-decompositions [18, 50, 51], polytope theory [44], and geometric
packing [3]. See also the surveys [10, 32, 46].

###  1.2 Results

Before stating our result, let us define the covering problem in more detail.
We define a _polygon_ $\mathcal{P}$ to be a compact region in the plane such
that the boundary $\partial\mathcal{P}$ is a closed, simple curve consisting
of finitely many line segments. We now define the problem Minimum Convex Cover
(MCC for brevity) as follows.

Instance: A polygon $\mathcal{P}$ represented as an array of the coordinates
of the corners in cyclic order, and a positive integer $k$. The corners have
rational coordinates.

Question: Do there exist $k$ convex polygons $Q_{1},\ldots,Q_{k}$ such that
$\bigcup_{i=1}^{k}Q_{i}=\mathcal{P}$?

We get the problem Minimum Triangle Cover by requiring that each piece $Q_{i}$
is a triangle. We can now state the main result of the paper.

######  Theorem 1.

Minimum Convex Cover and Minimum Triangle Cover are
$\exists\mathbb{R}$-complete.

Recall that O’Rourke [36] proved $\exists\mathbb{R}$-membership already in
1982. Alternatively, $\exists\mathbb{R}$-membership can be easily proven using
the recent framework by Erickson, van der Hoog, and Miltzow [22]. This paper
is therefore only concerned with proving $\exists\mathbb{R}$-hardness.

An implication of the result is that many natural approaches to finding small
covers are bound to give suboptimal solutions in some cases. One might attempt
to make covers consisting of pieces with corners chosen from some discrete set
of points inside the given polygon. For instance, Eidenbenz and Widmayer [20]
gave a $O(\log n)$-factor approximation algorithm for finding a minimum convex
cover for a polygon $\mathcal{P}$ by choosing pieces with corners from a set
of $O(n^{16})$ points. These points are obtained by first making the
arrangement of lines through all pairs of corners of $\mathcal{P}$. We then
construct all lines through pairs of intersection points in the first
arrangement. The intersection points of this final arrangement, of which there
are $O(n^{16})$, are the candidate set of corners of the pieces from which a
cover is constructed.

Eidenbenz and Widmayer showed that for this particular set, there exists a
cover consisting of at most $3$ times more pieces than in the unrestricted
optimum. Our result shows that the optimal solution cannot always be found by
choosing the corners from such a set of points, even if the process of making
new lines and intersection points was repeated any finite number of times. It
follows from our construction that there are polygons where the corners of
some pieces in any optimal cover have irrational coordinates with arbitrarily
high algebraic degree. As an example, we can consider an equation such as
$x^{5}-4x+2=0$ [6], which has one real solution and that solution cannot be
expressed by radicals (that is, the solution cannot be written using integers
and basic arithmetic operations including powers and roots). We can then
transform the equation to an instance of MCC, so that in the optimal cover,
some pieces have coordinates that cannot be expressible by radicals. We state
this as a corollary to our construction, to be proven in Section 3.14.

######  Corollary 2.

There exists a polygon $\mathcal{P}$ such that in any minimum convex cover for
$\mathcal{P}$, a piece has a corner with a coordinate that is not expressible
by radicals.

###  1.3 Structure of the paper and basic techniques

We prove that Etr reduces to MCC using two intermediate problems: Range-Etr-
Inv and MRCC, which we define in Section 2. Essentially, an instance of Range-
Etr-Inv is a conjunction of addition constrains of the form $x+y=z$ and
inversion constraints of the form $x\cdot y=1$. Each variable is restricted to
a tiny subinterval of $[\frac{1}{2},2]$, and the goal is to decide if there
exist values of the variables that satisfy all the addition and inversion
constraints. This problem was developed recently in order to prove
$\exists\mathbb{R}$-hardness of geometric packing problems [3].

The problem MRCC is a technical version of MCC where only some crucial parts
of the polygon have to be covered, namely a specific set of _marked corners_
and a set of _marked rectangles_. The introduction of the problem MRCC is
crucial in order to keep our reductions manageable. In Section 2, we define
the problem and give a reduction from MRCC to MCC. In the proof, we show that
everything else than the marked corners and rectangles can be covered in a
generic way by adding some spikes to the boundary of the polygon. We therefore
get an instance of MCC which is equivalent to the instance of MRCC that we are
reducing from.

In Section 3, we give the reduction from Range-Etr-Inv to MRCC, which is the
major part of the work. We do reductions in reversed order so that the reader
can get a better understanding of the problem MRCC, and the rationale for
introducing it, before seeing the rather long reduction from Range-Etr-Inv to
MRCC. In Section 4, we conclude the paper by outlining how triples of
collinear corners can be avoided in our construction and mentioning an open
problem.

Figure 2: Representing variables in the paper [2] and this paper. Left: A
guard segment $s$ with a guard representing the value $1$. When the guard
moves to the right, more visibility is blocked due to the corner $d$. Middle:
A piece covering the marked corner $c$ represents the value $1$ on the
variable segment $s$. By rotating the dashed edge around the corner $d$, more
or less of $s$ will be covered. Right: Several variable segments can be
partially covered by a single piece and then “copied” into different gadgets
by the orange propagation pieces.

One of our basic tools in the reduction to MRCC is to represent variables
using specific horizontal _variable segments_ contained in the constructed
polygon; see Figure 2. A segment $s$ representing a variable $x$ corresponds
to the interval $[1/2,2]$ of values that $x$ can attain, with the endpoints
representing $x=1/2$ and $x=2$. The values of points in between the endpoints
are defined by linear interpolation. A part of a segment $s$ must be covered
by a piece $Q$ that also covers a particular marked corner of the polygon. The
right-most (or left-most) point in the intersection $s\cap Q$ defines the
value that $Q$ represents on $s$. The rest of $s$ must then be covered by
another piece (which also covers another marked corner).

In the bottom of the polygon, we have some _base pockets_ containing variable
segments representing all the variables. We describe gadgets for addition
inequalities, $x+y\geq z$ and $x+y\leq z$, and inversion inequalities, $x\cdot
y\geq 1$ and $x\cdot y\leq 1$, and these gadgets are placed far to the right
and above the base pockets. The gadgets also contain variable segments. We
create some corridors that connect the gadgets and the base pockets, and they
ensure that if a cover exists, then appropriate inequalities hold between the
values represented in the base pockets and those in the gadgets. We are
therefore able to conclude that if a cover exists, then so does a solution to
the instance of Range-Etr-Inv that we are reducing from.

Our reduction shares some resemblance with that from [2], and many of the
geometric tools underlying our construction are similar to the ones used in
that paper. In [2], variables are also represented by segments in the polygon,
but the actual value is defined by the position of a guard standing on the
segment (as shown in Figure 2), whereas in our case, it is the left- or right-
most point covered by a convex piece. The geometric principles underlying the
addition and inversion gadgets are the same in the two papers, but again the
actual realizations of the gadgets are very different.

A key insight is that one convex piece in a base pocket can partially cover
any number of variable segments, and thus represent numerous copies of the
same variable, as sketched in Figure 2 (right). Each of these segments will
have its own _propagation corner_ , which is a marked corner. The propagation
corner can then be covered by a _propagation piece_ , which must cover the
remaining part of the segment. Each propagation piece is very long and thin
and sticks into a corridor far away. This is needed so that a variable that
appears in many addition and inversion constraints can be copied into all the
corresponding gadgets. In contrast to this, the reduction to Art Gallery in
[2] relied on the fact that a single guard can _look_ into several different
corridors. That technique is not possible to realize with convex pieces,
because points in different corridors cannot see each other and hence no
convex piece covers points in more than one corridor.

##  2 Auxilliary problems: Range-Etr-Inv and MRCC

In this section we introduce the two problems Range-Etr-Inv and MRCC that will
be used as intermediate problems in our reduction from Etr to MCC.

###  2.1 Range-Etr-Inv

######  Definition 3.

An _Etr-Inv formula_ $\Phi=\Phi(x_{1},\ldots,x_{n})$ is a conjunction

$\left(\bigwedge_{i=1}^{n}1/2\leq x_{i}\leq
2\right)\land\left(\bigwedge_{i=1}^{m}C_{i}\right),$

where $m\geq 0$ and each $C_{i}$ is of one of the forms

$\displaystyle x+y=z,\quad x\cdot y=1$

for $x,y,z\in\\{x_{1},\ldots,x_{n}\\}$.

We can now define the problem Range-Etr-Inv as follows.

Instance: A tuple
$\mathcal{I}=\left[\Phi,\delta,(I(x_{1}),\ldots,I(x_{n}))\right]$, where
$\Phi$ is an Etr-Inv formula, $\delta>0$ is a (small) number, and, for each
variable $x\in\\{x_{1},\ldots,x_{n}\\}$, $I(x)$ is an interval
$I(x)\subseteq[1/2,2]$ such that $|I(x)|\leq\delta$. Define
$V(\Phi):=\\{\mathbf{x}\in\mathbb{R}^{n}:\Phi(\mathbf{x})\\}$. We are promised
that $V(\Phi)\subset I(x_{1})\times\cdots\times I(x_{n})$.

Question: Is $V(\Phi)\neq\emptyset$?

The following theorem establishes that it suffices to make a reduction from
Range-Etr-Inv in order to prove that MCC is $\exists\mathbb{R}$-hard.

######  Theorem 4 ([3]).

Range-Etr-Inv is $\exists\mathbb{R}$-complete, even when $\delta=O(n^{-c})$
for any constant $c>0$.

###  2.2 Minimum Restricted Convex Cover (MRCC)

We now turn our attention to the problem Minimum Restricted Convex Cover
(MRCC). As we will see later in this section, MRCC can be reduced to MCC.
Therefore, $\exists\mathbb{R}$-hardness for MRCC implies the same hardness for
MCC. We define MRCC as follows.

Instance: A tuple $\langle\mathcal{P},\mathcal{C},\mathcal{R}\rangle$
consisting of the following parts:

  * •

A simple polygon $\mathcal{P}$.

  * •

A subset $\mathcal{C}=\\{c_{1},c_{2},\ldots,c_{k}\\}$ of the corners of
$\mathcal{P}$ called _marked corners_.

  * •

A set of pairwise disjoint axis-parallel rectangles
$\mathcal{R}=\\{R_{1},\ldots,R_{m}\\}$ contained in $\mathcal{P}$, called
_marked rectangles_.

Question: Do there exist $k=|\mathcal{C}|$ convex polygons
$Q_{1},\ldots,Q_{k}$ contained in $\mathcal{P}$ such that
$\mathcal{C}\subset\bigcup Q_{i}$ and $R\subset\bigcup Q_{i}$ for all marked
rectangles $R\in\mathcal{R}$?

An instance of MRCC comes with a promise which we will explain below. In order
to state the promise, we need some notation. For a corner $c$ of a polygon
$\mathcal{P}$, define $\Delta(c)$ to be the triangle with corners at $c$ and
the two neighbouring corners of $\mathcal{P}$. Note that $\Delta(c)$ may not
be contained in $\mathcal{P}$, but that will always be the case when we use
the notation.

For a marked rectangle $R\in\mathcal{R}$, define the _vertical bar_
$\Pi_{v}(R)$ to be the region of points that are vertically visible from $R$,
i.e., the points $p\in\mathcal{P}$ such that there is a point $q\in R$ where
$pq$ is a vertical line segment contained in $\mathcal{P}$. In a similar way,
we define the _horizontal bar_ $\Pi_{h}(R)$ as the points that are
horizontally visible from $R$; see Figure 3.

In order to define the _vertical trapezoidation_ of a polygon $\mathcal{P}$,
we consider for each corner $c$ of $\mathcal{P}$ the vertical segment that (i)
contains $c$, (ii) is contained in $\mathcal{P}$, and (iii) is maximal with
respect to inclusion. These segments partition $\mathcal{P}$ into trapezoids,
some of which are only triangles. The _horizontal trapezoidation_ is defined
similarly, using horizontal segments.

Figure 3: A polygon with a marked rectangle $R$ the vertical and horizontal
bars shown.

##### Promise.

For the instances
$\mathcal{I}=\langle\mathcal{P},\mathcal{C},\mathcal{R}\rangle$ of MRCC that
we will consider, we promise that the following properties hold, which we call
the _MRCC promise_. For convenience, we have named each individual point of
the promise.

  1. 1.

_Skew triangle promise:_ For each marked corner $c$, the triangle $\Delta(c)$
intersects the vertical and the horizontal line containing $c$ only at the
point $c$.

  2. 2.

_Trapezoid generality promise:_ In any trapezoid $T$ in the vertical
trapezoidation of $\mathcal{P}$, at least one right corner of $T$ is not a
corner of $\mathcal{P}$, unless the right corners of $T$ are coincident (so
that $T$ is a triangle). Similarly for the left corners. Likewise, in any
trapezoid in the horizontal trapezoidation, at least one top corner is not a
corner of $\mathcal{P}$ unless they are coincident, and similarly for the
bottom corners.

  3. 3.

_Bar intersection promise:_ For any two marked rectangles $R_{i}$ and $R_{j}$,
the vertical bar of $R_{i}$ and the horizontal bar of $R_{j}$ are either
disjoint or their intersection is contained in a marked rectangle.

  4. 4.

_Broad cover promise:_ If $\mathcal{I}$ has a cover, then there also exists a
cover $\mathcal{Q}$ for $\mathcal{I}$ such that
$\Delta(c)\subset\bigcup_{Q\in\mathcal{Q}}Q$ for all $c\in\mathcal{C}$.

######  Lemma 5.

Suppose that Minimum Restricted Convex Cover is $\exists\mathbb{R}$-hard, even
when restricted to instances satisfying the MRCC promise. Then Minimum Convex
Cover is also $\exists\mathbb{R}$-hard.

###### Proof.

Let $\mathcal{I}:=\langle\,\mathcal{P},\mathcal{C},\mathcal{R}\,\rangle$ be an
instance of MRCC that satisfies the promise. We first describe the high-level
idea behind our reduction to MCC. We construct a larger polygon
$\mathcal{P}^{\prime}\supset\mathcal{P}$ by adding some number $s$ of spikes
to $\mathcal{P}$. A _spike_ is a triangle $S$ which is interior-disjoint from
$\mathcal{P}$ and such that the intersection $S\cap\mathcal{P}$ is an edge of
$S$, which we call the _base_ of the spike. The corner of $S$ opposite of the
base is called the _tip_ of the spike $S$. The polygon $\mathcal{P}^{\prime}$
will be defined as
$\mathcal{P}^{\prime}:=\mathcal{P}\cup\bigcup_{S\in\mathcal{S}}S$, where
$\mathcal{S}$ is a set of $s$ spikes. The spikes in $\mathcal{S}$ may overlap,
but we choose them such that $\mathcal{P}^{\prime}$ has no holes.

We then get the instance
$\mathcal{I}^{\prime}:=\langle\,\mathcal{P}^{\prime},k^{\prime}\,\rangle$ of
MCC, where the parameter $k^{\prime}$ is defined as $k^{\prime}:=k+s$ with
$k:=|\mathcal{C}|$. As we will see, our reduction implies that a cover for
$\mathcal{I}^{\prime}$ using $k^{\prime}=k+s$ convex polygons contains $s$
polygons covering the added spikes. The spikes have been chosen so that they
cannot be covered while also covering $\mathcal{R}$ nor $\mathcal{C}$, so the
remaining $k$ polygons must cover $\mathcal{R}$ and $\mathcal{C}$ and thus
constitute a cover for $\mathcal{I}$. On the other hand, given a cover
$\mathcal{Q}$ for $\mathcal{I}$, one can add $s$ convex polygons contained in
$\mathcal{P}^{\prime}$ that cover the spikes and everything else of
$\mathcal{P}^{\prime}$ not covered by $\mathcal{Q}$, and thus obtain a cover
for $\mathcal{I}^{\prime}$. Therefore, the instances are equivalent.

To carry out this idea, we consider a vertical and a horizontal trapezoidation
of (parts of) $\mathcal{P}$ and in each trapezoid $T$, we add two or three
spikes such that these spikes and $T$ can be covered with two or three
triangles. Let us explain the horizontal trapezoidation first. Define
$\mathcal{T}^{\prime}_{h}$ as the horizontal trapezoidation of the polygons
$\mathcal{P}^{\prime}_{h}:=\mathcal{P}\setminus\bigcup\Pi_{h}(R_{j})$.
Consider a marked corner $c$. Because of point 1 of the promise of
$\mathcal{I}$, $c$ is contained in a unique trapezoid of
$\mathcal{T}^{\prime}_{h}$, which is in fact a triangle
$\Delta^{\prime}(c)\subseteq\Delta(c)$. We then define
$\mathcal{T}_{h}:=\mathcal{T}^{\prime}_{h}\setminus\\{\Delta^{\prime}(c)\mid
c\in\mathcal{C}\\}$ as all the other trapezoids. Likewise, we define
$\mathcal{P}_{h}:=\bigcup_{T\in\mathcal{T}_{h}}T$ as the region covered by the
other trapezoids.

We now add _horizontal_ spikes to each trapezoid $T$ of $\mathcal{T}_{h}$ as
shown in Figure 4. We must ensure that each added spike is interior-disjoint
from $\mathcal{P}$ to avoid “collisions”. This limits how long the spikes can
be. We say that a corner of $T$ is _free_ if it is not also a corner of
$\mathcal{P}$. Let us first consider a non-degenerate trapezoid $T$, i.e., $T$
is not a triangle. If a corner $c$ is not free, we should avoid to add a spike
there, as the edge of $\mathcal{P}$ incident at $c$ outside $T$ may cause a
collision. Because of point 2 of the promise of $\mathcal{I}$, we know that a
top corner and a bottom corner of $T$ are free. If one is on the left side and
the other on the right side of $T$ we can add two spikes, so that two
triangles can cover the spikes and all of $T$, but nothing else of
$\mathcal{P}$. If the top and bottom free corners are on the same side, we add
two spikes on that side on one in the middle of the opposite side so that the
three triangles can cover the three spikes and all of $T$, but nothing else.

If $T$ is a triangle, we add two spikes as shown, so that two triangles can
cover the spikes and $T$, but nothing else.

Figure 4: The figure shows how we add spikes to trapezoids in the horizontal
trapezoidation $\mathcal{T}_{h}$. The fat edges are edges of $\mathcal{P}$ and
the dots show the corners of $\mathcal{P}$, i.e., the corners that are not
free. Left: When there is a free left and right corner, we add two spikes such
that $T$ and the two spikes can be covered by two triangles. Middle: When
there is no free left corner (as shown here) or no free right corner, we add
three spikes. Right: When the trapezoid is a triangle, we add two spikes as
shown.

A problem can occur when we want to make two horizontal spikes that share a
horizontal side due to two neighbouring trapezoids $T_{1}$ and $T_{2}$ where
$T_{1}$ is above $T_{2}$, as shown in Figure 5. This results in a degenerate
polygon with a corner with an interior angle of $2\pi$, or a non-functional
merged spike, depending on the viewpoint. We may assume without loss of
generality that the bottom edge of $T_{1}$ is at least as long as the top edge
of $T_{2}$. We then move the spike of $T_{2}$ up and place it along the side
of $T_{1}$. The trapezoid $T_{2}$ and its spikes can now be covered with
triangles that also cover a part of $T_{1}$, but nothing else of
$\mathcal{P}$.

Figure 5: Left: Two spikes share a horizontal edge and make a degenerate
polygon. Right: We move the spike of $T_{2}$ up and get two well-defined
spikes.

We then consider the vertical trapezoidation $\mathcal{T}^{\prime}_{v}$ of the
polygons $\mathcal{P}^{\prime}_{v}:=\mathcal{P}\setminus\bigcup\Pi_{v}(R_{j})$
and again define $\mathcal{T}_{v}$ by removing the triangles containing the
marked corners from $\mathcal{T}_{v}$ and $\mathcal{P}_{v}$ as the union of
the trapezoids in $\mathcal{T}_{v}$. We then add _vertical_ spikes to the
trapezoids $\mathcal{T}_{v}$ in an analogous way. Here, the horizontal and the
vertical spikes may overlap, but we need to be careful that we do not
introduce holes when we define $\mathcal{P}^{\prime}$ as the union of
$\mathcal{P}$ and all the spikes. A hole is introduced if and only if a
horizontal and a vertical spike overlap and the spikes have disjoint bases.
Such an overlap can be avoided by making the vertical spike sufficiently short
so that it does not reach the horizontal spike; see Figure 6.

Figure 6: Left: In order to avoid introducing a hole when we add spikes, we
make the vertical spike $s_{v}$ so short that it does not intersect the
horizontal spike $s_{h}$. Right: Two spikes $s_{v}$ and $s_{h}$ overlap in an
acceptable way without creating a hole.

We now claim that

$\displaystyle\mathcal{P}\setminus\left(\bigcup
R_{j}\cup\bigcup\Delta(c_{i})\right)\subset\mathcal{P}_{v}\cup\mathcal{P}_{h}.$
(1)

To see this, we consider a point $p\in\mathcal{P}\setminus(\bigcup
R_{j}\cup\bigcup\Delta(c_{i}))$. If $p$ is not in the vertical or the
horizontal bar of any marked rectangle, then $p$ is in both $\mathcal{P}_{v}$
and $\mathcal{P}_{h}$. Otherwise, suppose that $p\in\Pi_{v}(R)$ for some
$R\in\mathcal{R}$. Since $p$ is not in any marked rectangle, we get from point
3 in the promise of $\mathcal{I}$ that $p$ is not in any horizontal bar of a
marked rectangle. Hence, $p\in\mathcal{P}_{h}$. Likewise, if $p\in\Pi_{h}(R)$
for $R\in\mathcal{R}$, we get that $p\in\mathcal{P}_{v}$.

It remains to verify that the instances $\mathcal{I}$ and
$\mathcal{I}^{\prime}:=\langle\mathcal{P}^{\prime},k^{\prime}\rangle$ are
equivalent. Suppose first that $\mathcal{I}$ has a cover $\mathcal{Q}$ of size
$k:=|\mathcal{C}|$. By point 4 of the promise of $\mathcal{I}$, we can assume
that for each $c\in\mathcal{C}$, the whole triangle $\Delta(c)$ is covered by
$\mathcal{Q}$. We define $\mathcal{Q}^{\prime}$ to be the cover we get by
adding to $\mathcal{Q}$ for each spike the maximal triangle in
$\mathcal{P}^{\prime}$ that contains the spike. Then $\mathcal{Q}^{\prime}$
consists of $k^{\prime}:=k+s$ polygons, where $s$ is the number of spikes, and
we need to verify that
$\bigcup_{Q\in\mathcal{Q}^{\prime}}Q=\mathcal{P}^{\prime}$. Clearly, for every
$Q\in\mathcal{Q}^{\prime}$, we have $Q\subset\mathcal{P}^{\prime}$, so we just
need to check that every point $p$ in $\mathcal{P}^{\prime}$ is in some
polygon $Q\in\mathcal{Q}^{\prime}$. If
$p\in\mathcal{P}^{\prime}\setminus\mathcal{P}$, then $p$ is in a spike and is
thus covered. If $p\in\Delta(c)$ for $c\in\mathcal{C}$ or $p\in R$ for
$R\in\mathcal{R}$, then it follows from the properties of the cover
$\mathcal{Q}$ of $\mathcal{I}$ that $p$ is covered by $\mathcal{Q}$ and thus
by $\mathcal{Q}^{\prime}$. In the remaining case, we have
$p\in\mathcal{P}\setminus(\bigcup R_{j}\cup\bigcup\Delta(c_{i}))$, so we get
from (1) that $p\in\mathcal{P}_{v}$ or $p\in\mathcal{P}_{h}$. Then $p$ is in a
trapezoid $T$ of $\mathcal{T}_{h}$ or $\mathcal{T}_{v}$, so $p$ is in a
triangle of $\mathcal{Q}^{\prime}$ that also covers one of the spikes of $T$.

Suppose then that $\mathcal{P}^{\prime}$ has a cover $\mathcal{Q}^{\prime}$ of
size $k^{\prime}$. We claim that $s$ polygons in $\mathcal{Q}^{\prime}$ are
used to cover the spikes. Although the tips of some spikes see each other, we
can assume that no polygon in $\mathcal{Q}^{\prime}$ covers two spike corners,
for the following reason: Two tips that see each other must be tips of spikes
added to the same trapezoid in $\mathcal{T}_{v}$ or $\mathcal{T}_{h}$. The
only convex set that covers two such tips is a line segment. But that means
that if $Q\in\mathcal{Q}^{\prime}$ covers two tips, then $Q$ is a line
segment, and then $\mathcal{Q}^{\prime}\setminus\\{Q\\}$ must cover all of
$\mathcal{P}^{\prime}$. Hence, we can assume that each tip is covered by a
unique polygon in $\mathcal{Q}^{\prime}$. We conclude that $s$ polygons are
used to cover the spikes.

By construction, each tip sees nothing outside
$\mathcal{P}_{v}\cup\mathcal{P}_{h}$. Therefore, the remaining $k$ polygons in
$\mathcal{Q}^{\prime}$ must cover
$\mathcal{P}\setminus(\mathcal{P}_{v}\cup\mathcal{P}_{h})$. Since no marked
corner is contained in $\mathcal{P}_{v}\cup\mathcal{P}_{h}$ and
$\mathcal{P}_{v}\cup\mathcal{P}_{h}$ is interior-disjoint from each marked
rectangle, we have that $k$ polygons cover $\mathcal{C}$ and $\mathcal{R}$.
Hence, $\mathcal{I}$ has a cover. ∎

##  3 Reduction from Range-Etr-Inv to MRCC

Let $\mathcal{I}_{1}$ be an instance of Range-Etr-Inv with an Etr-Inv formula
$\Phi$ of $n$ variables $X:=\\{x_{1},\ldots,x_{n}\\}$. We show that there
exists an instance
$\mathcal{I}_{2}:=\langle\,\mathcal{P},\mathcal{C},\mathcal{R}\,\rangle$ of
MRCC which can be computed in polynomial time such that $\Phi$ has a solution
if and only if $\mathcal{I}_{2}$ has a cover. Recall that a cover
$\mathcal{Q}$ of $\mathcal{I}_{2}$ is a set of $|\mathcal{C}|$ convex polygons
contained in $\mathcal{P}$ that together cover the marked corners
$\mathcal{C}$ and the marked rectangles in $\mathcal{R}$. A high-level sketch
of the polygon $\mathcal{P}$ is shown in Figure 7.

Figure 7: A high-level sketch of our construction. The polygon $\mathcal{P}$
will have dimensions quadratic in $N$, which is proportional to the size of
the Etr-Inv instance $\Phi$.

###  3.1 Basic tools

Before describing the actual geometry of the instance $\mathcal{I}_{2}$, we
explain the basic tools that underlie our construction.

####  3.1.1 Invisibility property

We make sure that our constructed instance $\mathcal{I}_{2}$ satisfies the
following _invisibility property_ : No two marked corners can see each other.

For a marked corner $c\in\mathcal{C}$, let $e_{1}$ and $e_{2}$ be the two
edges of $\mathcal{P}$ incident at $c$. Except for one marked corner in each
$\leq$-inversion gadget, it holds that $c$ is the lower endpoint of both
$e_{1}$ and $e_{2}$. The invisibility thus follows for all other corners.
Additionally, it holds without exception that $c$ is either the left endpoint
of both $e_{1}$ and $e_{2}$ or the right endpoint of both.

Note that since a cover $\mathcal{Q}$ for $\mathcal{I}_{2}$ consists of
$|\mathcal{C}|$ pieces and no piece can cover more than one marked corner by
the invisibility property, it follows that each piece $Q\in\mathcal{Q}$
contains exactly one marked corner $c\in\mathcal{C}$.

####  3.1.2 Critical segments and the bi-cover property

In the instance $\mathcal{I}_{2}$ that we construct, a marked rectangle
$R\in\mathcal{R}$ often contains a special line segment $s$ which we call a
_critical segment_ ; see Figure 8. The following property turns out to be
crucial, and we call it the _bi-cover property_ : For each critical segment
$s$, there are at least two and at most three marked corners that can see $s$.
There are three if and only if $s$ is not horizontal, and in that case, one of
these three corners $h$ is a _helper corner_ (to be described later), and $h$
is incident to an edge contained in the extension of $s$. In particular, $s$
is on the boundary of the visibility polygon of $h$. Otherwise, if $s$ is
horizontal, then $s$ is a variable segment, to be described in more detail
below.

Figure 8: Left: A horizontal critical segment $s$ contained in the bottom edge
of its marked rectangle $R$. Two pieces cover $R$ and the responsible lever
corners $c_{1}$ and $c_{2}$. Right: A critical segment that is not horizontal.
We use a helper corner $h$ with an incident edge contained in the extension of
$s$. The three pieces cover $R$ and the responsible lever corners
$c_{1},c_{2}$ and the helper corner $h$.

A critical segment will always be contained in a marked rectangle, but we will
also make some marked rectangles that do not contain critical segments. Often
these are introduced to satisfy the bar intersection promise of the MRCC
instance, and they will be defined as the intersection of a vertical and a
horizontal bar of two other marked rectangles. Another example is the marked
rectangle $R_{\Gamma^{\prime}}$ in each addition gadget, to be explained in
Section 3.10.

Consider a critical segment $s$ and the marked rectangle $R$ containing $s$.
Let $c_{1},c_{2}\in\mathcal{C}$ be the marked corners that see $s$ and are not
helper corners. These are called _lever corners_ , and we say that $c_{1}$ and
$c_{2}$ are _responsible_ for $s$ and for the marked rectangle $R$. Since a
cover for $\mathcal{I}_{2}$ must cover all of the rectangle $R$, it follows
from the invisibility property and the bi-cover property that $c_{1}$ and
$c_{2}$ must be covered by two pieces $Q_{1}$ and $Q_{2}$ that also together
cover $s$. All the marked corners that we make will be either helper corners
or lever corners. A piece that covers a lever corner is called a _lever piece_
and otherwise it is a _helper piece_.

####  3.1.3 Helper corners

As mentioned above, we will make two types of marked corners, namely lever
corners and helper corners. Furthermore, we will make two kinds of helper
corners. In general, we make a helper corner when a marked rectangle or a part
of a marked rectangle cannot be covered by lever pieces. One situation is when
we introduce a marked rectangle with the sole purpose of satisfying the bar
intersection promise described in Section 2.2; see Figure 9 for an example.

The other situation is when we have a marked rectangle $R$ containing a
critical segment $s$ which is not horizontal; see Figure 8 (right). In this
case, the two pieces $Q_{1}$ and $Q_{2}$ covering the lever corners $c_{1}$
and $c_{2}$ responsible for $s$ can cover the part of $R$ above or below $s$,
but they cannot cover everything on the other side. We then make a helper
corner $h$ so that one of the edges incident at $h$ is contained in the
extension of $s$. Thus, $s$ is on the boundary of the visibility polygon of
$h$, and a piece covering $h$ can cover the part of $R$ on the other side of
$s$.

If a critical segment $s$ is horizontal, we make the marked rectangle $R$ so
that $s$ is contained in the bottom or top edge of $R$, as seen in Figure 8
(left). Then the pieces covering the responsible corners $c_{1}$ and $c_{2}$
will be able to cover all of $R$ without the use of a helper corner.

Figure 9: In order to satisfy the bar intersection promise, we make a marked
rectangle $R_{h}$ which is the intersection of the horizontal bar of $R_{1}$
and the vertical bar of $R_{2}$. We then make a helper corner $h$ so that a
piece covering $h$ can also cover $R_{h}$.

####  3.1.4 Representing variables

Each variable $x\in X$ is represented by a collection of _variable segments_ ,
which are horizontal critical segments. Consider one variable segment $s:=ab$
where $a$ is to the left of $b$, and assume that $s$ represents $x$. The
segment $s$ can be oriented either to the left or to the right. Each point $p$
on $s$ represents a value of $x$ in the interval $[\frac{1}{2},2]$, which we
denote as $\mathbf{x}(s,p)$. If $s$ is right-oriented, then we define
$\mathbf{x}(s,p):=1/2+\frac{3\|ap\|}{2\|ab\|}$, and otherwise we define
$\mathbf{x}(s,p):=1/2+\frac{3\|bp\|}{2\|ab\|}$. In particular,
$\mathbf{x}(s,\cdot)$ is a linear map from $s$ to $[\frac{1}{2},2]$.

Consider a variable segment $s$ and a lever corner $c$ responsible for $s$. In
a cover $\mathcal{Q}$ for $\mathcal{I}_{2}$, the piece $Q$ covering $c$
specifies a value at $s$, defined as follows. Each lever corner comes with a
_pivot_ which is also a corner of $\mathcal{P}$. Let $d$ be the pivot of $c$.
It is then always the case that $d$ has another $y$-coordinate than $s$. For a
point $q\in s$, consider the line $\overleftrightarrow{qd}$ through $q$ and
the pivot $d$, which is never horizontal by the previous remark, so the line
has a well-defined left and right side. Furthermore, it will be the case that
whether $c$ is to the right or left of $\overleftrightarrow{qd}$ does not
depend on the particular point $q$. We say that $c$ is the _right-responsible_
or _left-responsible_ for $s$, depending on this side. For instance, in Figure
11, $c_{c}$ is right-responsible and $c_{b}$ is left-responsible for the
segment $s_{3}$.

If $c$ is a right-responsible, then we define $\mathbf{p}_{\mathcal{Q}}(s,c)$
as the leftmost point in $Q\cap s$ (or the right endpoint of $s$ if $Q\cap
s=\emptyset$). Otherwise, we define $\mathbf{p}_{\mathcal{Q}}(s,c)$ as the
rightmost point in $Q\cap s$ (or the left endpoint of $s$ if $Q\cap
s=\emptyset$). We now define the value represented by $\mathcal{Q}$ at $s$
with respect to $c$ as
$\mathbf{v}_{\mathcal{Q}}(s,c):=\mathbf{x}(s,\mathbf{p}_{\mathcal{Q}}(s,c))$.
We will usually use the simplified notation $\mathbf{p}(s,c)$ and
$\mathbf{v}(s,c)$ if $\mathcal{Q}$ is clear from the context.

Recall that for each critical segment $s$, there are two responsible lever
corners $c_{1},c_{2}$, so that in a cover for $\mathcal{I}_{2}$, the pieces
covering $c_{1}$ and $c_{2}$ must together cover $s$. It will always be the
case in our construction that one is left-responsible and the other is right-
responsible. We then have the following observation.

######  Observation 6.

Consider a variable segment $s:=ab$, where $a$ is the left endpoint, and let
$c_{1}$ be the left-responsible for $s$ and $c_{2}$ the right-responsible.
Consider any cover $\mathcal{Q}$. Since the pieces covering $c_{1}$ and
$c_{2}$ also cover $s$, we have $\mathbf{p}(s,c_{2})\in a\mathbf{p}(s,c_{1})$.
It follows that if $s$ is right-oriented, then
$\mathbf{v}(s,c_{1})\geq\mathbf{v}(s,c_{2})$. Otherwise,
$\mathbf{v}(s,c_{1})\leq\mathbf{v}(s,c_{2})$.

We are now ready to state the theorem that expresses that our reduction works
as desired.

######  Theorem 7.

Suppose that there is a solution to $\Phi$. Then our constructed instance
$\mathcal{I}_{2}:=\langle\,\mathcal{P},\mathcal{C},\mathcal{R}\,\rangle$ has a
cover, and any cover $\mathcal{Q}$ of $\mathcal{I}_{2}$ _specifies_ a solution
to $\Phi$, as described by the following two properties.

  * •

Each variable $x\in X$ is specified _consistently_ by $\mathcal{Q}$: For each
variable segment $s$ representing $x$, consider the corners
$c_{1},c_{2}\in\mathcal{C}$ that are responsible for $s$. Then
$\mathbf{x}(s,c_{1})=\mathbf{x}(s,c_{2})$, and this value is the same for all
segments $s$ representing $x$.

  * •

The cover $\mathcal{Q}$ is _feasible_ , i.e., the values of $X$ thus specified
is a solution to $\Phi$.

On the other hand, if there is no solution to $\Phi$, then there is no cover
for $\mathcal{I}_{2}$. The instance $\mathcal{I}_{2}$ can be computed in time
polynomial in the input size $|\mathcal{I}_{1}|$. It thus follows that MRCC is
$\exists\mathbb{R}$-complete.

####  3.1.5 Lever mechanism

The basic mechanism of our construction is similar to that of a lever (as
known from mechanics) and works as follows; see Figure 10. As mentioned
earlier, a marked corner will either be a helper corner or a _lever corner_ ,
and each lever corner has a _pivot_ $d$, which is also a corner of
$\mathcal{P}$ but not a marked corner. The two corners $c$ and $d$ can always
see each other. There is also a set of marked rectangles
$\mathcal{S}:=\\{R_{1},\ldots,R_{l}\\}$, $l\geq 2$, for which $c$ is one of
the responsible corners. In particular, the rectangles $\mathcal{S}$ can be
seen from $c$. One or more of the rectangles
$\mathcal{S}_{t}:=\\{s_{1},\ldots,s_{m}\\}$, $m<l$, are above $d$ and one or
more $\mathcal{S}_{b}:=\\{s_{m+1},\ldots,s_{l}\\}$ are below $d$. Recall that
some marked rectangles contain variable segments. The variable segments
contained in the rectangles $\mathcal{S}$ all represent the same variable
$x\in X$, and the variable segments in $\mathcal{S}_{t}$ have the same
orientation, which is the opposite of that of the variable segments in
$\mathcal{S}_{l}$.

Figure 10: A lever piece partially covering the associated marked rectangles,
each of which contains a variable segment. Two overlapping and maximal lever
pieces are shown, and the lever edge of one of them is shown as a dashed
segment.

A piece of a cover for $\mathcal{I}_{2}$ that covers a lever corner $c$ is
called a _lever piece_. A lever piece $Q$ can cover a part of the rectangles
$\mathcal{S}$, but the pivot $d$ is preventing $Q$ from covering all the
rectangles entirely. Suppose that we want the piece $Q$ to have non-empty
intersection with all rectangles in $\mathcal{S}$ and cover as much as
possible of each one. Such a piece must have an edge $e$ that contains $d$, as
we could otherwise cover more of the top rectangles $\mathcal{S}_{t}$ or the
bottom rectangles $\mathcal{S}_{b}$. We say that $e$ is a _lever edge_ , and
$e$ has the property that it intersects all the rectangles $\mathcal{S}$.
Furthermore, the lever piece $Q$ contains the part of each rectangle $R$ on
the same side of $e$, either to the left (if $c$ is the left-responsible for
the rectangles $\mathcal{S}$) or to the right (if $c$ is the right-
responsible). We can now imagine that the edge $e$ rotates around the pivot
$d$. Doing so, the piece $Q$ will cover more of the top rectangles
$\mathcal{S}_{t}$ and less of the bottom rectangles $\mathcal{S}_{b}$, or vice
versa.

Consider the subset $\mathcal{S}^{\prime}\subseteq\mathcal{S}$ that contain
critical segments (the reader can conveniently imagine the case
$\mathcal{S}^{\prime}=\mathcal{S}$; the only exception will be in the addition
gadgets). Then there are two _range lines_ , both of which pass through $d$,
and each critical segment in $\mathcal{S}^{\prime}$ has an endpoint on each
range line. When the lever edge of $Q$ coincides with a range line, then the
critical segments in one of the sets $\mathcal{S}_{b}$ or $\mathcal{S}_{t}$
are completely covered, while the segments in the other set are not covered at
all.

Figure 11: Three lever corners and lever pieces that together cover the
variable segments $s_{2}$ and $s_{3}$.

####  3.1.6 Chains of inequalities

The following observation follows immediately from the description above and
is one of our main tools for copying values from one variable segment to
another.

######  Observation 8.

Let $R_{t}\in\mathcal{S}_{t}$ and $R_{b}\in\mathcal{S}_{b}$ be two marked
rectangles and assume that they contain variable segments $s_{t}$ and $s_{b}$,
respectively. Suppose that the lever corner $c$ is the right-responsible for
both $s_{t}$ and $s_{b}$. If $s_{t}$ is right-oriented and $s_{b}$ is left-
oriented, then $\mathbf{v}(s_{t},c)\geq\mathbf{v}(s_{b},c)$. If $s_{t}$ is
left-oriented and $s_{b}$ is right-oriented, then
$\mathbf{v}(s_{t},c)\leq\mathbf{v}(s_{b},c)$. If on the other hand $c$ is the
left-responsible, then the inequalities are swapped. Equalities hold if and
only if $Q$ has a lever edge, and then $Q$ represents the same value on all
variable segments in $\mathcal{S}$.

Using chains of lever mechanisms, we can now make chains of inequalities of
the values that the lever pieces represent of a variable $x\in X$, using
Observations 6 and 8 alternatingly. See for instance Figure 11. The
observations give
$\mathbf{v}(s_{1},c_{a})\leq\mathbf{v}(s_{2},c_{a})\leq\mathbf{v}(s_{2},c_{b})\leq\mathbf{v}(s_{3},c_{b})\leq\mathbf{v}(s_{3},c_{c})\leq\mathbf{v}(s_{4},c_{c})$.
The figure shows the case that $Q_{a},Q_{b},Q_{c}$ all have lever edges
(containing the pivots $d_{a},d_{b},d_{c}$, respectively) and cover $s_{2}$
and $s_{3}$ with no overlap, and then we have equalities
$\mathbf{v}(s_{1},c_{a})=\mathbf{v}(s_{2},c_{a})=\mathbf{v}(s_{2},c_{b})=\mathbf{v}(s_{3},c_{b})=\mathbf{v}(s_{3},c_{c})=\mathbf{v}(s_{4},c_{c})$.
Otherwise, one or more of the inequalities will be strict.

Figure 12: The (light and dark) blue arrows show the full variable segments
representing a variable $x$ and the dark blue parts are the parts
corresponding to the restricted range $I(x)$. To the left, the dotted lever
edge has enough freedom to rotate over the entire restricted range, since the
corner $c$ sees all points on the restricted ranges of the variable segments.
To the right, $c$ does not see all of the upper restricted range $s^{\prime}$,
so not all values can be represented.

####  3.1.7 Infinitesimal range

Recall that each variable $x\in X$ comes with an interval
$I(x)\subset[\frac{1}{2},2]$ of size $|I(x)|\leq\delta$, for some small
$\delta$, such that all solutions to $\Phi$ are guaranteed to be contained in
these intervals. In this reduction, we use $\delta:=n^{-7}$. Consider a
variable segment $s$ representing $x$. Let $s^{\prime}$ be the part of $s$
such that the points of $s^{\prime}$ correspond to the range $I(x)$. We then
call $s^{\prime}$ the _restricted range_ of $s$, and since $\delta:=n^{-7}$,
we have that $\frac{\|s^{\prime}\|}{\|s\|}=O(n^{-7})$. Since we can assume $n$
to be arbitrarily large, we can usually think of $s^{\prime}$ as being just a
single point on $s$. In our construction, we will always show the full segment
$s$ in the figures, and we will mark the position of the restricted range
$s^{\prime}$ as a single point on $s$. We just need to ensure that the
construction is generic in the sense that it works for every possible
placement of the restricted range $s^{\prime}$ on the full range $s$. In
particular, when we construct a lever corner $c\in\mathcal{C}$, it may be
needed to move $c$ and the edges of $\mathcal{P}$ incident at $c$ depending on
where the restricted range $s^{\prime}$ is located at $s$.

We need the lever corner $c$ to be placed so that it can see all points on the
restricted range $s^{\prime}$ of $s$. When that is the case for all segments
$s$ that $c$ is responsible for, then a lever edge of a piece covering $c$
will have the freedom to rotate over all of $s^{\prime}$, thus representing
all values in the required range $I(x)$. See Figure 12 for examples with
enough freedom and too little freedom.

In many parts of our construction, it is obvious that $c$ can see all of the
restricted ranges of the variable segments. The more delicate case happens for
the propagation corners, to be described in more detail in the next section.
These are responsible for variable segments in the base pockets, but also for
critical segments in the corridors. Here, it is not clear that the propagation
corners can see enough of the critical segments in the corridors, but as we
will see in Section 3.7, it works for our choice of $\delta:=n^{-7}$.

We choose the marked rectangles to be similarly tiny, as they only need to
contain the restricted ranges of the critical segments. Hence, the vertical
and horizontal bars of the rectangles can be thought of as vertical or
horizontal line segments contained in $\mathcal{P}$.

###  3.2 High-level description of $\mathcal{P}$

Name | Description/value
---|---
$\mathcal{I}_{1}:=\langle\,\Phi,\delta,(I(x_{1}),\ldots,I(x_{n}))\,\rangle$ | instance of Range-Etr-Inv that we reduce from
$\mathcal{I}_{2}:=\langle\,\mathcal{P},\mathcal{C},\mathcal{R}\,\rangle$ | instance of MRCC that we reduce to
$X:=\\{x_{1},\ldots,x_{n}\\}$ | set of variables of $\Phi$
$n$ | number of variables in $\Phi$
$\Phi_{\text{ineq}}$ | formula equivalent to $\Phi$ using only inequalities
$X_{\text{ineq}}:=\\{x_{1},\ldots,x_{3n}\\}$ | variables of $\Phi_{\text{ineq}}$
$\delta$ |  $n^{-7}$, maximum range of each variable $x_{i}$
$\mathcal{P}:=\mathcal{P}(\Phi)$ | final polygon to be constructed from $\Phi$
$C$ | a sufficiently large constant
$N$ | maximum index of a variable segment $s_{i}$ in the base pockets, $N=O(n^{3})$
$s_{i}:=a_{i}b_{i}$ | variable segment in a base pocket, $i\in\\{1,\ldots,N\\}$
$c_{i}^{s}$ | propagation corner of the segment $s_{i}:=a_{i}b_{i}$
$o$ |  $c_{1}^{s}$, relative origin of the base pockets
$\eta$ |  $1/32$, every variable segment $s_{i}$ has a length in $[\frac{3}{2}(1-\eta),\frac{3}{2}]$
corridor | connection between the main part of $\mathcal{P}$ and a gadget
$d_{0}d^{0},d_{1}d^{1}$ | corridor doors, $d^{0}:=d_{0}+(0,\frac{4.5}{CN^{2}})$ and $d^{1}:=d_{1}+(0,\frac{2.25}{CN^{2}})$
$\ell_{\widehat{o}}$ | vertical line through the point $\frac{d_{0}+d_{1}}{2}$
$\widehat{o}$ | intersection of the ray $\overrightarrow{od_{0}}$ and $\ell_{\widehat{o}}$
$\bar{o}$ | point on $\overrightarrow{\widehat{o}d_{1}}$ with $x(\bar{o})=x(d_{1})+1$, relative origin of a particular gadget
$r_{i},r_{j},r_{l}$ | variable segments within gadgets
$\bar{a}_{\sigma},\bar{b}_{\sigma}$, $\sigma\in\\{i,j,l\\}$ | left and right endpoint of $r_{\sigma}$, $\sigma\in\\{i,j,l\\}$
$c_{\sigma}^{r}$ | right lever corner responsible for $r_{\sigma}:=\bar{a}_{\sigma}\bar{b}_{\sigma}$
$\nu$, $\rho$ , $\varepsilon$ |  $\nu:=\frac{13.5}{CN^{2}}$, $\rho:=\frac{\nu}{9}=\frac{1.5}{CN^{2}}$, $\varepsilon:=\frac{\rho}{48}=\frac{1}{32CN^{2}}$
$\widehat{V}$ |  $\widehat{o}+[-N\nu,N\nu]\times[-N\nu,N\nu]$, square in a corridor
slab $S(q,v,r)$ | region of all points with distance at most $r$ to the line through $q$
| with direction $v$
center of slab | line in the middle of a slab
$L$-slabs, $R$-slabs | uncertainty regions for visibility rays, see Section 3.6.2
Table 1: Parameters, variables, and certain distances that are frequently used
are summarized in this table for easy access. Some descriptions are much
simplified.

We are now ready to describe the actual design of the polygon $\mathcal{P}$ in
more detail; see Figure 7 for a sketch of the entire polygon and Table 1 for
some of the terms and symbols that are often used. In the bottom of
$\mathcal{P}$, there are pockets with lever corners representing all the
variables; see Figure 13. Each pocket is a polygon in $\mathcal{P}$ bounded by
a chain of $\partial\mathcal{P}$ and from above by one horizontal chord of
$\mathcal{P}$. A pocket can contain a large number of variable segments
$\mathcal{S}$, all representing the same variable $x\in X$. In the lower right
corner of the pocket, there is a lever corner, which we call a _base corner_ ,
and which is the right-responsible lever corner for all the segments
$\mathcal{S}$. A piece covering a base corner is called a _base piece_. For
each variable segment, the left-responsible lever corner is called a
_propagation corner_. The pivot of a propagation corner is very far away
approximately in direction $(1,1)$, namely at the door of a corridor that
leads into a gadget. A piece covering a propagation corner is called a
_propagation piece_ , and in any cover, the propagation pieces will be very
skinny and long, sticking out of the base pockets and into the corridors,
where each of them is responsible for covering another critical segment.

Figure 13: Left: A sketch of three consecutive base pockets with various
numbers of variable segments. The variable segments are shown as red dots.
Right: A closeup of three consecutive variable segments and the marked
rectangles containing them.

The bottom part of $\mathcal{P}$ consists of a collection of $3n$ base
pockets. In order from left to right, we denote the pockets as
$P_{1},\ldots,P_{3n}$. The pockets $P_{1},\ldots,P_{n}$ represent the
variables $x_{1},\ldots,x_{n}$, respectively, as do the pockets
$P_{n+1},\ldots,P_{2n}$, and $P_{2n+1},\ldots,P_{3n}$. At the right side of
$\mathcal{P}$, there are some _corridors_ attached, each of which leads into a
_gadget_. The _doors_ to the corridors are line segments contained in a
vertical line $\ell_{r}$ (in fact, we will move the doors slightly away from
$\ell_{r}$ in order to satisfy the trapezoid generality promise, but that does
not make any conceptual difference). The gadgets also contain marked
rectangles and corners, and they are used to impose dependencies between the
pieces covering variable segments in the base pockets. The corridors are used
to make dependencies between the base pockets and the gadgets. Each gadget
corresponds to a constraint of one of the types $x+y\geq z$, $x+y\leq z$,
$x\cdot y\geq 1$, $x\cdot y\leq 1$, and $x\leq y$. The first four types of
constraints are used to encode the dependencies between the variables in $X$
as specified by $\Phi$, whereas the latter constraint is used to make sure
that the three base pockets representing a variable $x\in X$ specify the value
of $x$ consistently.

The reason that we need three pockets $P_{i},P_{i+n},P_{i+2n}$ representing
each variable $x_{i}$ is that in the addition gadgets, such as the one
encoding the restriction $x_{i}+x_{j}\geq x_{l}$, we need the base pockets
representing $x_{l},x_{j},x_{i}$, that we connect to the gadget, to appear in
the specific order $P_{i^{\prime}},P_{j^{\prime}},P_{l^{\prime}}$ from left to
right, respectively. This is obtained by choosing $i^{\prime}:=i$,
$j^{\prime}:=j+n$, and $l^{\prime}:=l+2n$.

###  3.3 Detailed construction of the bottom wall

In this section we present the construction of the bottom wall of
$\mathcal{P}$. Recall that the bottom wall forms $3n$ base pockets
$P_{1},\ldots,P_{3n}$, such that a variable $x_{i}$ is represented by the
pockets $P_{i},P_{n+i},P_{2n+i}$. Each pocket may contain multiple variable
segments.

We define a formula $\Phi_{\text{ineq}}$ equivalent to the Etr-Inv-formula
$\Phi$ in the following way. We formally introduce $2n$ new variables
$x_{n+1},\ldots,x_{3n}$, such that each pocket $P_{i}$ represents just one
variable $x_{i}$, for $i\in\\{1,\ldots,3n\\}$. We define
$X_{\text{ineq}}:=\\{x_{1},\ldots,x_{3n}\\}$ as the total set of variables.
For each $i\in\\{1,\ldots,n\\}$, we introduce the three constraints $x_{i}\geq
x_{n+i}$, $x_{n+i}\geq x_{2n+i}$, and $x_{2n+i}\geq x_{i}$. These ensure that
$x_{i}=x_{n+i}=x_{2n+i}$, which corresponds to the pockets
$P_{i},P_{n+i},P_{2n+i}$ specifying the same value of a variable. We rewrite
every occurrence of $x_{i}+x_{j}=x_{l}$ as two inequalities:

$x_{i}+x_{n+j}\geq x_{2n+l}\text{\quad and\quad}x_{i}+x_{n+j}\leq x_{2n+l}.$

This is to ensure that for all addition inequalities, the indices of the
appearing variables have a specific order. Likewise, we rewrite every
occurrence of $x_{i}x_{j}=1$ as two inequalities:

$x_{i}x_{n+j}\geq 1\text{\quad and\quad}x_{i}x_{n+j}\leq 1.$

To sum up, we now have a formula $\Phi_{\text{ineq}}$ equivalent to $\Phi$,
and $\Phi_{\text{ineq}}$ is a conjunction of inequalities of the forms

$x_{i}+x_{j}\geq x_{l},\quad x_{i}+x_{j}\leq x_{l},\quad x_{i}x_{j}\geq
1,\quad x_{i}x_{j}\leq 1,\quad x_{i}\geq x_{j},$

where $i,j,l\in\\{1,\ldots,3n\\}$. The last inequality is only used to ensure
$x_{i}=x_{n+i}=x_{2n+i}$ for each $i\in\\{1,\ldots,n\\}$, as described before.
For each addition inequality, we have $i<j<l$, and for each multiplication
inequality we have $i<j$. We have two different types of inequalities of the
form $x_{i}\geq x_{j}$, namely those where $i<j$ and those where $j<i$. We can
assume that there are at most $O(n^{3})$ inequalities in $\Phi_{\text{ineq}}$,
as otherwise some inequalities would be identical.

Consider a variable $x_{i}$, $i\in\\{1,\ldots,3n\\}$, and the appearances of
the variable in the inequalities of $\Phi_{\text{ineq}}$, rewritten as
described above. We associate each appearance of $x_{i}$ to a distinct
variable segment in the pocket $P_{i}$. For each inequality $\xi$, there will
be a gadget $G_{\xi}$ that enforces the base pockets to obey the inequality
$\xi$. The variable segments associated to the appearances of the variables in
$\xi$ will be connected to $G_{\xi}$ via a corridor. Whether the segments
associated to $\xi$ should be right- or left-oriented will be clear when the
individual gadgets are described in detail.

Recall that a variable segment has endpoints on the two range lines, so the
length of the segment depends on its $y$-coordinate. We want all variable
segments in the base pockets to have a length in the range
$[\frac{3}{2}(1-\eta),\frac{3}{2}]$, for the small constant
$\eta:=\frac{1}{32}$. A pocket has to be dimensioned correctly in order to
accommodate enough segments of this length. To keep the construction simpler,
we make all the pockets equally large, and this size is chosen so that all
pockets can accommodate their segments. The construction of the bottom wall
will therefore depend on the pocket that receives the largest number $k$ of
variable segments with the same orientation.

We place the right-oriented segments above the pivot and the left-oriented
below the pivot. In each pocket, we place the variable segments with the same
orientation equidistantly with vertical distance $13.5$, with the right-
oriented segments in the top and the left-oriented in the bottom; see Figure
13. We therefore choose the height of the pockets to be $13.5k/\eta$. This
ensures that even in the pocket with most segments of the same orientation, we
can place the right-oriented segments within distance $13.5k$ from the top and
the left-oriented segments within distance $13.5k$ from the bottom, and then
the length of the shortest will be at least $1-\eta$ times the longest. We
choose the width of the pockets slightly larger than the height, so that rays
with direction $(1,1)$ from the bottom-most variable segment in one pocket are
not obstructed by the pocket. This is important since we are going to place
the gadgets so that the propagation pieces will follow approximately the
direction $(1,1)$. Furthermore, the rays from the bottom-most segment in
pocket $P_{i}$ will then be above the rays from the top-most segment in the
pocket $P_{i+1}$ to the right. Note that since $\eta$ is small, the range
lines (i.e., the two lines through the pivot that together contain all
endpoints of the segments in one base pocket) will be close to vertical and
the variable segments will appear as a vertical stack of equally long
segments.

We place the base pockets so that all pivots are on a horizontal line and the
distance between two consecutive pivots is a multiple of $13.5$, and we place
the variable segments so that the topmost segments in all pockets are on a
horizontal line, as are the bottom-most. We want to enumerate the variable
segments according to the slope of the direction to any particular corridor.
We place the segments such that for each segment $s$, the midpoint is
vertically above or below the pivot of the base pocket. It then follows that
these midpoints also have $x$-coordinates that are multiples of $13.5$. For a
particular variable segments with midpoint $p=(x(p),y(p))$, we then give a
_score_ defined as $x(p)-y(p)$. This ensures that every variable segments gets
a distinct score which is a multiple of $13.5$. Let $w_{\min}$ and $w_{\max}$
be the minimum and maximum scores, respectively, among all segments in all
pockets. We then denote a variable segment with score $w$ as $s_{i}$ where
$i:=(w-w_{\min})/13.5+1$. Let $N:=(w_{\max}-w_{\min})/13.5+1$, so that each
segment $s_{i}$ has an index $i\in\\{1,\ldots,N\\}$. Many of these indices are
unused, because we only placed segments close to the top and bottom of each
pocket and because the pockets are wider than they are high. We have that
$N=O(n^{3})$, since each variable can participate in at most $O(n^{2})$
different gadgets, so there are at most $O(n^{2})$ segments in each base
pocket, and there are $O(n)$ base pockets.

We define the left and right endpoints of the segment to be $a_{i}$ and
$b_{i}$, where $a_{i}$ is to the left. Consider a variable segment $s_{i}$ and
let the midpoint be $p$. We then define the associated propagation corner of
$s_{i}$ as $c_{i}^{s}:=p+(-13/4,-1)$. We choose the neighbouring corners to be
$c_{i}^{s}+(1,\frac{1}{8})$ and approximately $c_{i}^{s}+(1,1)$ (the precise
way to choose this second corner will be described in Section 3.7).

It will be convenient to define the relative origin of the base pockets to be
the first propagation corner $o:=c_{1}^{s}$. We then have the following
observation by the above description:

######  Observation 9.

For each $i\in\\{1,\ldots,N\\}$, if the segment $s_{i}$ exists, there exists
$\mu\in[0,\eta/2]$ such that the following holds:

  * •

$c_{i}^{s}$ is on the line through $o+(13.5(i-1),0)$ with direction $(1,1)$,

  * •

$a_{i}$ is on the line through $o+(13.5(i-1)+1.5+\mu,0)$ with direction
$(1,1)$,

  * •

$b_{i}$ is on the line through $o+(13.5(i-1)+3-\mu,0)$ with direction $(1,1)$.

###  3.4 Consistent variable representation in base pockets

Before we explain how to make corridors and gadgets, let us assume that we
already have them at hand and show how we can finish the construction using
them. Recall that we have rewritten the original Range-Etr-Inv formula $\Phi$
with variables $X:=\\{x_{1},\ldots,x_{n}\\}$ as a formula $\Phi_{\text{ineq}}$
with variables $X_{\text{ineq}}:=\\{x_{1},\ldots,x_{3n}\\}$, so that in all
solutions and for each $x_{i}\in X$, we will have $x_{i}=x_{i+n}=x_{i+2n}$.
Each variable $x_{i}\in X_{\text{ineq}}$ is represented by a base pocket
$P_{i}$, and the pockets appear in the order $P_{1},\ldots,P_{3n}$ from left
to right in the bottom of $\mathcal{P}$. In order to ensure that the base
triangles in the pockets $P_{i},P_{i+n},P_{i+2n}$ represent the same value of
$x_{i},x_{i+n},x_{i+2n}$, we make use of $\geq$\- and $\leq$-gadgets as
described in the following and shown schematically in Figure 14. (The gadgets
will be described in Sections 3.8 and 3.9.)

In the base pockets, the variable segments above the pivots are right-oriented
and the ones below the pivots are left-oriented. We connect the bottom-most
segment of $P_{i}$ and the topmost in $P_{i+n}$ with a $\geq$-inequality
gadget, and connect $P_{i+n}$ and $P_{i+2n}$ in a similar way. We connect the
topmost segment in $P_{i}$ and the bottommost in $P_{i+2n}$ with a
$\leq$-inequality gadget. We then have a cycle of inequalities that ensure
that the base triangles in the three pockets $P_{i},P_{i+n},P_{i+2n}$
represent the value of $x_{i}$ consistently on all variable segments in the
three pockets.

When we add the addition and inversion gadgets, the values of the variables
$X$ represented by the base triangles must satisfy all the constraints in
$\Phi$. It follows that if there is a cover for $\mathcal{I}_{2}$, then there
exists a solution to $\Phi$. On the other hand, if there is a solution to
$\Phi$, we get a corresponding cover where the pieces represent the given
solution. Thus, Theorem 7 follows.

Figure 14: Schematic view of how we connect the base pockets representing the
same variable $x_{i}$ using inequality gadgets. This creates a cycle of
inequalities so that the blue base triangles must represent the value of
$x_{i}$ consistently on all variable segments in the pockets.

###  3.5 Technique for connecting base pockets and gadgets

We already saw in Section 3.1 how we can make chains of inequalities using
variable segments that are covered pairwise by lever pieces. When connecting
the base pockets and the gadgets, it is advantageous to introduce some
critical segments that are not horizontal and hence not variable pieces
according to our definition. In this section, we explain the technique behind
using these critical segments. Such a segment $s$ will, however, represent a
variable $x\in X$, but the map from $s$ to $[\frac{1}{2},2]$ will not be
linear but some other rational function. In Section 3.6 we show how to use the
technique to make a corridor that can connect multiple variable segments in
the base pockets to segments in a gadget.

To capture the dependencies that a critical segment can make between the two
lever pieces covering it, we introduce the notion of projections. Consider a
lever corner $c$ and two critical segments $s_{0}$ and $s_{1}$ such that $c$
is responsible for both. Let $d$ be the pivot of $c$. For $p\in s_{0}$, we
define $\pi(p):=\overleftrightarrow{pd}\cap s_{1}$, and we say that the
function $\pi:s_{0}\longrightarrow s_{1}$ thus defined is the _projection_
from $s_{0}$ to $s_{1}$. Using generalizations of Observations 6 and 8, we get
the following, illustrated in Figure 15.

Figure 15: Left: If the pieces $Q_{0}$ and $Q_{1}$ cover all of $f_{0}f_{1}$,
then the leftmost point of $s_{1}$ covered by $Q_{1}$ is on the segment
$p_{1}b_{1}$. Right: Lemma 11 says that when $y(d_{0})=y(d_{1})$, then
$\mathbf{x}(s_{0},p_{0})=\mathbf{x}(s_{1},p_{1})$.

######  Observation 10.

Consider a critical segment $f:=f_{0}f_{1}$ and let $c_{0}$ be the left-
responsible for $f$ and $c_{1}$ the right-responsible. Let $d_{0},d_{1}$ be
the pivots of $c_{0},c_{1}$, respectively, and suppose that $f$ is above both
$d_{0}$ and $d_{1}$. Let $s_{0}:=a_{0}b_{0}$ and $s_{1}:=a_{1}b_{1}$ be
variable segments below $d_{0}$ and $d_{1}$ for which $c_{0}$ and $c_{1}$ are
responsible, such that $a_{0},a_{1}$ are the left endpoints and
$f_{0}=\overrightarrow{b_{0}d_{0}}\cap\overrightarrow{b_{1}d_{1}}$ and
$f_{1}=\overrightarrow{a_{0}d_{0}}\cap\overrightarrow{a_{1}d_{1}}$. Let
$\pi_{0}$ be the projection from $s_{0}$ to $f$ and $\pi_{1}$ be that from $f$
to $s_{1}$. Consider any cover $\mathcal{Q}$, and let
$p_{0}:=\mathbf{p}(s_{0},c_{0})$ and $p_{1}:=\pi_{1}(\pi_{0}(p_{0}))$. Then
$f\cap Q_{0}\subset f_{0}\pi(p_{0})$, and therefore $\pi(p_{0})f_{1}\subset
Q_{1}$. We then have $s_{1}\cap Q_{1}\subset p_{1}b_{1}$. In particular, if
$s_{1}$ is right-oriented, then
$\mathbf{v}(s_{1},c_{1})\geq\mathbf{x}(s_{1},p_{1})$, and otherwise,
$\mathbf{v}(s_{1},c_{1})\leq\mathbf{x}(s_{1},p_{1})$.

The principle behind the following special case was also used in [2]; see
Figure 15 (right) for an illustration, and Figure 16 for an example of how we
make a helper spike in order to cover the bounding rectangle $R$ of the
critical segment $f$. Although the context in which we state the lemma is
different, the proof is analogous to one given in [2], so we give the lemma
without proof.

######  Lemma 11 ([2]).

In the setup of Observation 10, if $y(d_{0})=y(d_{1})$, then
$\mathbf{x}(s_{0},p_{0})=\mathbf{x}(s_{1},p_{1})$. In particular, if $s_{0}$
and $s_{1}$ both right-oriented, then
$\mathbf{v}(s_{0},c_{0})\leq\mathbf{v}(s_{1},c_{1})$, and if $s_{0}$ and
$s_{1}$ both left-oriented, then
$\mathbf{v}(s_{0},c_{0})\geq\mathbf{v}(s_{1},c_{1})$.

Figure 16: The setting of Lemma 11. Let $x_{0},x_{1}$ be the values specified
by $U_{0}$ and $U_{1}$ on $r_{0}$ and $r_{1}$, respectively. Then $x_{0}\geq
x_{1}$.

###  3.6 Corridor for copying variable segments into a gadget

In this section, we describe the construction of a corridor, the purpose of
which is to make inequalities between variable segments from the base pockets
and a gadget. Inside each gadget there are three (or two) variable segments
$r_{i},r_{j},r_{l}$ (or $r_{i},r_{j}$) corresponding to three (or two)
variable segments from the base pockets $s_{i},s_{j},s_{l}$ (or
$s_{i},s_{j}$). For each $\sigma\in\\{i,j,l\\}$, we say that $s_{\sigma}$ and
$r_{\sigma}$ are _partners_. The pairs of partners is a matching between the
variable segments in the base pockets and those in the gadgets. We require
that for each $\sigma\in\\{i,j,l\\}$ the partners $s_{\sigma},r_{\sigma}$ have
the same orientation since this is required for the way we implement
inequalities, as described by Lemma 11.

We assume $i<j<l$. We describe here how to construct a corridor that ensures
that we have inequalities between the segments $r_{i},r_{j},r_{l}$ and the
segments $s_{i},s_{j},s_{l}$, respectively. For any
$\sigma\in\\{1,\ldots,N\\}$, recall that $c_{\sigma}^{s}$ is the propagation
corner responsible for $s_{\sigma}$, and for each $\sigma\in\\{i,j,l\\}$,
define $c_{\sigma}^{r}$ to be the lever corner responsible for $r_{\sigma}$ to
the right, which will be a corner inside the gadget containing $r_{\sigma}$.
It will follow from Lemma 11 that if $r_{\sigma}$ and $s_{\sigma}$ are right-
oriented, then
$\mathbf{v}(s_{\sigma},c_{\sigma}^{s})\leq\mathbf{v}(r_{\sigma},c_{\sigma}^{r})$.
Otherwise, if they are both left-oriented, we will have
$\mathbf{v}(s_{\sigma},c_{\sigma}^{s})\geq\mathbf{v}(r_{\sigma},c_{\sigma}^{r})$.

The construction of the corridor relies on similar techniques as described in
[2]. In [2] it was described how to get equality between values represented on
each of the pairs of guard segments
$(s_{i},r_{i}),(s_{j},r_{j}),(s_{l},r_{l})$. In our case, it will suffice to
ensure that there is an inequality between the values, using Lemma 11. This
makes the upper wall of our corridor simpler.

The construction can be generalized for making inequalities between an
arbitrary subset of variable segments, but since the gadgets we use only
handle two or three variable segments at a time, we explain the construction
only in the setting of three segments. The construction for two segments is
analogous but simpler.

The lower wall of the corridor of the gadget is a horizontal edge $d_{0}d_{1}$
of length $2$, where $d_{0}$ is on the vertical line $\ell_{r}$ and $d_{1}$ is
to the right of $d_{0}$. The upper wall of the corridor is more complicated,
and it will be described later. It has the left endpoint at
$d^{0}:=d_{0}+(0,\frac{4.5}{CN^{2}})$, and the right endpoint
$d^{1}:=d_{1}+(0,\frac{2.25}{CN^{2}})$. We refer to the vertical line segments
$d_{0}d^{0}$ and $d_{1}d^{1}$ as the _doors_ of the corridor.

####  3.6.1 The principles of the corridor construction

Figure 17: This figure sketches the corridor construction in a much simplified
manner. The corner $d_{0}$ serves as a pivot for $s_{i},s_{j},s_{l}$ as well
as the three critical segments $f_{i},f_{j},f_{l}$, and $d_{1}$ serves as a
pivot for $r_{i},r_{j},r_{l}$ and $f_{i},f_{j},f_{l}$. The doors $d_{0}d^{0}$
and $d_{1}d^{1}$ to the corridor are sufficiently small so that the critical
segment $f_{\sigma}$ of the pair $s_{\sigma},r_{\sigma}$ are not seen by the
responsible corners of other segments, so they must be covered by pieces
covering the corners $c_{\sigma}^{s}$ and $c_{\sigma}^{r}$.

Figure 17 sketches the construction of the corridor. The corridor contains
three critical segments $f_{i},f_{j},f_{l}$, such that the responsible corners
of $f_{\sigma}$ is $c_{\sigma}^{s}$ and $c_{\sigma}^{r}$. For each
$\sigma\in\\{i,j,l\\}$, the corner $c_{\sigma}^{s}$ is left-responsible for
$s_{\sigma}$ and for $f_{\sigma}$, with the pivot $d_{0}$. Similarly,
$c_{\sigma}^{r}$ is right-responsible for $r_{\sigma}$ and $f_{\sigma}$ and
has pivot $d_{1}$. We construct the chain of $\mathcal{P}$ from $d^{0}$ to
$d^{1}$ bounding the corridor from above so that a reflex corner goes down in
between the critical segments which blocks the visibility between the critical
segments. This is to make sure that we satisfy the bar intersection promise
described in Section 2.2 (that is, by preventing that bars from different
marked rectangles overlap, we do not have to introduced more marked
rectangles).

The biggest challenge is to ensure the bi-cover invariant of the critical
segments $f_{i},f_{j},f_{l}$. In particular, that for each
$\sigma\in\\{i,j,l\\}$, the only marked corners that see $f_{\sigma}$ is the
propagation corner $c_{\sigma}^{s}$ responsible for $s_{\sigma}$ and the lever
corner $c_{\sigma}^{r}$ responsible for $r_{\sigma}$. This is obtained by
choosing the doors $d_{0}d^{0}$ and $d_{1}d^{1}$ correctly. In particular, we
will ensure that the vertical edge of $\mathcal{P}$ directly below the door
$d_{0}d^{0}$ blocks visibility from all propagation corners $c_{k}^{s}$ for
$k>\sigma$, from which the direction to $d_{0}$ is more vertical than from
$c_{\sigma}^{s}$. Likewise, the vertical edge of $\mathcal{P}$ directly above
$d_{0}d^{0}$ blocks visibility from all propagation corners $c_{k}^{s}$ for
$k<\sigma$, from which the direction is more horizontal than from
$c_{\sigma}^{s}$. The door $d_{1}d^{1}$ in the other side of the pocket
similarly ensures that only the intended corner $c_{\sigma}^{r}$ can see
$f_{\sigma}$. We can therefore establish the bi-cover invariant and use Lemma
11.

The main idea to achieve the above property is to make each door $d_{i}d^{i}$,
$i\in\\{0,1\\}$, of the corridor sufficiently small. However, we cannot place
the point $d^{0}$ arbitrarily close to $d_{0}$, since then $c_{\sigma}^{s}$
will not see enough of the critical segment $f_{\sigma}$, which is needed. By
placing the corridor sufficiently far away from the segments of the base
pockets, we obtain that the visibility lines from the propagation corners
$c_{\sigma}^{s}$ through the left door endpoints $d_{0},d^{0}$ are almost
parallel to each other and can be described by a simple pattern. The same
holds for the lines from the lever corners $c_{\sigma}^{r}$ in the gadgets
through the right door endpoints $d_{1},d^{1}$. The pattern enables us to
construct the corridor with the desired properties.

In the following, we introduce objects that make it possible to describe the
upper corridor wall and prove that the construction works as intended.

####  3.6.2 Describing visibilities in the corridor

Recall that $o:=c_{1}^{s}$ is the propagation corner of the first variable
segment $s_{1}$. We define the point $\widehat{o}$ as the point on the ray
$\overrightarrow{od_{0}}$ such that $x(\widehat{o})=x(d_{0})+1$. We consider
the rays from the propagation corners in the base pockets through one of the
points $d_{0}$ and $d^{0}$. They all pass through a small area around
$\widehat{o}$ and have directions close to $(1,1)$. Similarly, the rays from
the gadget (attached to the right of the corridor) through the points $d_{1}$
and $d^{1}$ pass through the same region around $\widehat{o}$, and they have
directions close to $(-1,1)$. In this section we introduce some thin slabs
with directions $(1,1)$ and $(-1,1)$, and these will contain the rays close to
$\widehat{o}$. The slabs will be used to reason about which lever corners can
see which critical segments in the corridor. Thus, the slabs are introduced in
order to handle the “uncertainty” and irregularity of the rays.

The analysis resembles that from [2], but is slightly more complicated, since
our variable segments have different lengths and are placed at different
heights contrary to the guard segments in [2] that are equally long and placed
equidistantly on a line. Furthermore, we need to consider the rays from the
propagation corners and variable segment endpoints, whereas in [2] only the
guard segment endpoints were considered. We therefore develop the more general
technical Lemma 12 below to deal with this complexity. The lemma is
illustrated in Figure 18.

Given a point $q$ and a vector $v\neq(0,0)$, the _slab_ $S(q,v,r)$ consists of
all points at distance at most $r$ from the line through $q$ parallel to $v$.
The _center_ of the slab $S(q,v,r)$ is the line through $q$ parallel to $v$.
Let us define vectors $\alpha:=(1,1)$ and $\beta:=(-1,1)$.

Figure 18: The setting of Lemma 12.

######  Lemma 12.

Let $B$ be the axis-parallel unit square with center $o:=(0,0)$. Let
$\Lambda>0$ and $\lambda>0$, and let $d$ be a point of the form
$\Lambda\alpha+(0,h)$ where $|h|\leq 1$. Let $\ell_{\widehat{o}}$ be the
vertical line with $x$-coordinate $\Lambda+\lambda$. Let $\widehat{o}$ be the
intersection of $\overrightarrow{od}$ and $\ell_{\widehat{o}}$ and let
$\widehat{B}$ be the axis-parallel square with center $\widehat{o}$ and edge
length $\lambda/\Lambda$. For a point $p$ to the left of $d$, define
$\widehat{p}:=\widehat{o}-p\lambda/\Lambda$. For some
$\varepsilon=O(\lambda/\Lambda^{2})$, it then holds that for every point $p\in
B$, we have $\overrightarrow{pd}\cap\widehat{B}\subset
S(\widehat{p},\alpha,\varepsilon)$.

###### Proof.

Let $\ell_{o}$ be the vertical line containing $o$. For a point $p\in B$, note
first that $\widehat{p}$ is on the line $\overleftrightarrow{pd}$. Let $q$ be
the intersection point of $\overleftrightarrow{pd}$ and $\ell_{o}$. Let $k$
and $\widehat{k}$ be the lines through $p$ and $\widehat{p}$, respectively,
with direction $\alpha$, and note that $\widehat{k}$ is the center of any slab
$S(\widehat{p},\alpha,\varepsilon)$. Let $z$ be the intersection point of
$\ell_{o}$ and $k$. We first bound the distance $\|\widehat{z}\widehat{q}\|$,
which is the vertical deviation between $\widehat{k}$ and
$\overrightarrow{pd}$ at $\ell_{\widehat{o}}$. Since the triangles
$\widehat{p}\widehat{z}\widehat{q}$ and $pzq$ are similar, we get

$\|\widehat{z}\widehat{q}\|=\|zq\|\frac{\|\widehat{p}\widehat{q}\|}{\|pq\|}=\|zq\|\lambda/\Lambda.$

Let $u$ be the intersection point of $\overrightarrow{zp}$ and the vertical
line through $d$. Since the triangles $pzq$ and $pud$ are similar, we get

$\|\widehat{z}\widehat{q}\|=\lambda/\Lambda\cdot\frac{\|pz\|\|du\|}{\|pu\|}.$

Here, we have $\|pz\|\leq 2$, $\|du\|=O(1)$, and
$\|pu\|\geq\sqrt{2}(\Lambda-1)>\Lambda-1$, so we get
$\|\widehat{z}\widehat{q}\|=O(\lambda/\Lambda^{2})$. This means that at the
line $\ell_{\widehat{o}}$, the ray $\overrightarrow{pd}$ is contained in the
slab $S(\widehat{p},\alpha,\varepsilon)$, for
$\varepsilon=O(\lambda/\Lambda^{2})$. The maximum deviation is realized when
$\widehat{p}$ is on the left or right edge of $\widehat{B}$, and then the
vertical distance between $\overrightarrow{pd}$ and $\widehat{k}$ is maximal
on the vertical line through the right or left edge of $\widehat{B}$,
respectively, which is at most twice the deviation at the center line
$\ell_{\widehat{o}}$. Hence, the ray $\overrightarrow{pd}$ is contained in the
slab $S(\widehat{p},\alpha,\varepsilon)$ for
$\varepsilon=O(\lambda/\Lambda^{2})$ in all of $\widehat{B}$. ∎

Define the endpoints $\bar{a}_{\sigma},\bar{b}_{\sigma}$ of the variable
segments in the gadget such that $r_{\sigma}=\bar{a}_{\sigma}\bar{b}_{\sigma}$
with $\bar{a}_{\sigma}$ to the left. Define the relative origin of the gadget
as $\bar{o}:=c_{l}^{r}$, which is the right lever corner responsible for the
segment $r_{l}$. We place the gadget so that the point $\bar{o}$ is on the ray
$\overrightarrow{\widehat{o}d_{1}}$ with $x(\bar{o})=x(d_{1})+1$.

Let us introduce a grid of slabs parallel to $\alpha$ and $\beta$. Recall that
there are variable segments $s_{i}$ for a subset of the indices
$i\in\\{1,\ldots,N\\}$. In the following we do not care whether a particular
segment $s_{i}$ exists or not. We make the construction such that even if they
all exist, the construction works, and then it will also work when some are
missing.

We will later (using Lemma 12) choose a constant $C$, and using that, we
define

$\nu:=\frac{13.5}{CN^{2}},\ \rho:=\frac{\nu}{9}=\frac{1.5}{CN^{2}}\text{, and
}\varepsilon:=\frac{\rho}{48}=\frac{1}{32CN^{2}}.$

For each $\sigma\in\\{1,\ldots,N\\}$ and $\gamma\in\\{0,1,2,3\\}$ we define a
slab

$L^{\gamma}_{\sigma}:=S(\widehat{o}+(0,(\sigma-1)\nu+\gamma\rho),\alpha,\varepsilon),$

which we denote as an _$L$ -slab_. Let $\tau(i):=2$, $\tau(j):=1$, and
$\tau(l):=0$. For each $\sigma\in\\{i,j,l\\}$ and $\gamma\in\\{0,1,2,3\\}$ we
define a slab

$R^{\gamma}_{\sigma}:=S(\,\widehat{o}+(0,\tau(\sigma)\nu+\gamma\rho),\beta,\varepsilon),$

which we denote as an _$R$ -slab_. See Figure 19 for an illustration of the
area where the $L$-slabs intersect the $R$-slabs.

In the case of gadgets with just two guard segments $r_{i},r_{j}$, we define
the relative origin of the gadget to be $\bar{o}:=c_{j}^{r}$, which we place
on the ray $\overrightarrow{\widehat{o}d_{1}}$ with $x(\bar{o})=x(d_{1})+1$,
and we define $\tau(i):=1$ and $\tau(j):=0$. Then, the $R$-slabs
$R_{\sigma}^{\gamma}$ are defined as above for $\sigma\in\\{i,j\\}$.

Figure 19: A part of the grid of $L$\- and $R$-slabs. Each slab is one line in
the grid. Full green lines are $L_{\sigma}^{0}$ and $R_{\sigma}^{0}$. Red
lines are $L_{\sigma}^{1}$ and $R_{\sigma}^{1}$. Black lines are
$L_{\sigma}^{2}$ and $R_{\sigma}^{2}$. Dashed green lines are $L_{\sigma}^{3}$
and $R_{\sigma}^{3}$.

Let $\widehat{V}$ be the square $\widehat{o}+[-N\nu,N\nu]\times[-N\nu,N\nu]$.
Let us denote by $\mathcal{L}$ all the rays with endpoints at a propagation
corner $c_{\sigma}^{s}$, $\sigma\in\\{1,\ldots,N\\}$, going through $d_{0}$ or
$d^{0}$, and rays with endpoints $a_{\sigma}$ or $b_{\sigma}$ through the
point $d_{0}$. We will use Lemma 12 to ensure that all rays in $\mathcal{L}$
are inside a predefined slab within the square $\widehat{V}$, which is made
precise by the following lemma.

######  Lemma 13.

We can choose $C$ large enough such that for any corridor to be attached to
the polygon $\mathcal{P}$, the following properties are satisfied.

  1. 1.

The intersection of any $L$-slab with the line $\ell_{\widehat{o}}$ is
contained in $V$.

  2. 2.

For each $\sigma\in\\{1,\ldots,N\\}$, it holds that
$\overrightarrow{c_{\sigma}^{s}d_{0}}\cap V\subset
L^{0}_{\sigma},\overrightarrow{a_{\sigma}d_{0}}\cap V\subset
L^{1}_{\sigma},\overrightarrow{b_{\sigma}d_{0}}\cap V\subset L^{2}_{\sigma}$,
and $\overrightarrow{c_{\sigma}^{s}d^{0}}\cap V\subset L^{3}_{\sigma}$.

###### Proof.

The first property follows since the centers of the slabs intersect
$\ell_{\widehat{o}}$ at the points
$\widehat{o},\widehat{o}+(0,\nu),\ldots,\widehat{o}+(0,(N-1)\nu)$.

To prove the second property, we use Lemma 12, where the square
$V:=c_{1}^{s}+[-13.5N,13.5N]\times[-13.5N,13.5N]$ plays the role as the unit
square $B$ and $\widehat{V}$ plays the role as $\widehat{B}$. In order to
apply the lemma, we therefore scale $V$, $\widehat{V}$, and all other objects
by a factor of $1/27N$. When using the lemma for the first three rays, we use
$d_{0}$ as $d$, and for the first last, we use $d^{0}$. Recall that each
variable segment in the base pockets has a length in the interval
$[(1-\eta)3/2,3/2]$ with $\eta:=1/32=\varepsilon CN^{2}$, and that the center
points of the variable segments in each pocket are on a vertical line. We get
from the lemma that choosing $C$ large enough, property 2 follows. ∎

Consider a gadget containing the variable segments
$r_{\sigma}:=\bar{a}_{\sigma}\bar{b}_{\sigma}$, $\sigma\in\\{i,j,l\\}$. Recall
that the relative origin of a gadget is the point $\bar{o}:=c_{l}^{r}$, which
is placed on the ray $\overrightarrow{\widehat{o}d_{1}}$ with
$x(\bar{o})=x(d_{1})+1$. We state properties of gadgets with three variable
segments $r_{i},r_{j},r_{l}$, but there are natural analogues for gadgets with
just two variable segments $r_{i},r_{j}$. The following observation, which is
analogous to Observation 9, will be clear from the construction of each
gadget.

######  Observation 14.

For each $\sigma\in\\{i,j,l\\}$, the following holds:

  * •

$c_{\sigma}^{r}$ is on the line through $\bar{o}+(-\tau(\sigma)\nu,0)$ with
direction $\beta$,

  * •

$\bar{b}_{i}$ is on the line through $\bar{o}+(-\tau(\sigma)\nu-\rho,0)$ with
direction $\beta$,

  * •

$\bar{a}_{i}$ is on the line through $\bar{o}+(-\tau(\sigma)\nu-2\rho,0)$ with
direction $\beta$.

We now get the following from lemma.

######  Lemma 15.

We have the following two properties.

  1. 1.

The intersection of any $R$-slab with the line $\ell_{\widehat{o}}$ is
contained in $V$.

  2. 2.

For each $\sigma\in\\{i,j,l\\}$, it holds that
$\overrightarrow{c_{\sigma}^{r}d_{1}}\cap V\subset
R^{0}_{\sigma},\overrightarrow{\bar{b}_{\sigma}d_{1}}\cap V\subset
R^{1}_{\sigma},\ \overrightarrow{\bar{a}_{\sigma}d_{1}}\cap V\subset
R^{2}_{\sigma}$, and $\overrightarrow{c_{\sigma}^{r}d^{1}}\cap V\subset
R^{3}_{\sigma}$.

###### Proof.

The first property follows since the centers of the slabs intersect
$\ell_{\widehat{o}}$ at the points
$\widehat{o},\widehat{o}+(0,\nu),\widehat{o}+(0,2\nu)$.

To prove the second property, we again use Lemma 12, but this time reflected
along a vertical axis. The square
$V:=c_{l}^{r}+[-N\nu,N\nu]\times[-N\nu,N\nu]$ plays the role as the unit
square $B$, and $\widehat{V}$ will play the role as $\widehat{B}$, so in order
to apply the lemma, we scale $V$, $\widehat{V}$, and all other objects by a
factor of $1/2N\nu=\frac{CN}{27}$. For the first three rays (that pass through
$d_{1}$), we use $d$ in the lemma as $d_{1}$. For the last one, we use
$d^{1}$. We then get from the lemma that choosing $C$ large enough, property 2
follows. ∎

We can now conclude the following, which is obvious from property 1 of Lemma
13 and property 1 of Lemma 15, since the directions $\alpha$ and $\beta$ of
the slabs have slopes $1$ and $-1$, respectively.

######  Lemma 16.

The intersection of any $L$-slab with any $R$-slab is contained in
$\widehat{V}$.

From Lemmas 13 and 15, we get that for each $\sigma\in\\{i,j,l\\}$, only the
lever corners $c_{\sigma}^{s}$ and $c_{\sigma}^{r}$ can see the critical
segment $f_{\sigma}$ of the pair $s_{\sigma},r_{\sigma}$. This is because the
rays from other lever corners through the door endpoints
$d_{0},d^{0},d_{1},d^{1}$ are contained in the wrong slabs by the lemmas. The
vertical edge above the corner $d^{0}$ blocks the visibility from corners
$c_{\sigma^{\prime}}^{s}$ for $\sigma^{\prime}<\sigma$, and the vertical edge
below $d_{0}$ blocks the visibility from corners $c_{\sigma^{\prime}}^{s}$ for
$\sigma^{\prime}>\sigma$, and unwanted visibilities from marked corners in the
gadget are likewise blocked by the edges incident at $d^{1}$ and $d_{1}$. It
now remains to complete the specification of the corridor and the gadget so
that indeed the corners $c_{\sigma}^{s}$ and $c_{\sigma}^{r}$ can see
$f_{\sigma}$ and so that the instance satisfies the MRCC promise.

####  3.6.3 Specification of the corridor

We are now ready to describe the exact construction of the corridor. As
mentioned before, the bottom wall is simply the horizontal line segment
$d_{0}d_{1}$. We first describe the approximate shape of the upper wall,
defined by a polygonal curve $\Psi$ connecting the points $d^{0}$ and $d^{1}$;
see Figure 20. We will then add some helper spikes to get the final polygonal
curve $\Psi^{\prime}$.

Figure 20: The construction of the upper corridor wall. The color scheme of
the slabs is as in Figure 19. The critical segments are blue. See Figure 21
for a closeup of the gray rectangle.

Note that in the corridor construction here we assume that $i<j<l$. In
particular, the $L$-slabs $L^{\gamma}_{l}$ are above the $L$-slabs
$L^{\gamma}_{j}$, which are above $L^{\gamma}_{i}$. For the $R$-slabs it is
the opposite, i.e., the $R$-slabs $R^{\gamma}_{l}$ are below the $R$-slabs
$R^{\gamma}_{j}$, which are below $R^{\gamma}_{i}$.

Figure 20 shows the grid of slabs and a sketch of the curve $\Psi$
approximating the upper wall (excluding most of the leftmost and rightmost
edge of $\Psi$, with endpoints at $d^{0}$ and $d^{1}$, respectively, since
they are too long to be pictured together with the middle segments). For
$\sigma\in\\{i,j,l\\}$, let $u_{\sigma}$ be the intersection point of the rays
$\overrightarrow{c_{\sigma}^{s}d^{0}}$ and
$\overrightarrow{c_{\sigma}^{r}d^{1}}$. Let $v_{ij}$ be the intersection point
of the rays $\overrightarrow{c_{i}^{s}d^{0}}$ and
$\overrightarrow{c_{j}^{r}d^{1}}$, and $v_{jl}$ the intersection point of the
rays $\overrightarrow{c_{j}^{s}d^{0}}$ and $\overrightarrow{c_{l}^{r}d^{1}}$.
The curve $\Psi$ is then a path defined by the points
$d^{0}u_{i}v_{ij}u_{j}v_{jl}u_{l}d^{1}$. By Lemma 13, the set
$\Psi\cap\widehat{V}$ is contained in the union of the $L$-slabs and the
$R$-slabs, as shown in Figure 20. Due to the relative position of the slabs
$L^{\gamma}_{l},L^{\gamma}_{j},L^{\gamma}_{i}$ and
$R^{\gamma}_{l},R^{\gamma}_{j},R^{\gamma}_{i}$ as discussed above, the curve
$\Psi$ is $x$-monotone, and the point $v_{ij}$ (resp. $v_{jl}$) has smaller
$y$-coordinate than the neighbouring points $u_{i},u_{j}$ (resp.
$u_{j},u_{l}$), i.e., the curve $\Psi$ always has a zig-zag shape resembling
the one from Figure 20. We therefore get that when adding marked rectangles
around the restricted critical segments as described in the following, the
vertical and horizontal bars are pairwise disjoint, satisfying the bar
intersection promise.

Figure 21: A closeup of the construction of a helper spike. The figure also
shows the restricted critical segment (dark blue) and the horizontal and
vertical bars (orange).

We obtain the final upper wall $\Psi^{\prime}$ by adding helper spikes, as
shown in Figure 21: We consider the extension of each critical segment in the
direction of decreasing $y$-coordinates. We hit a segment of $\Psi$, and make
a helper spike there, with a corner that can see the region below the critical
segment. This ensures that the created helper corner is the bottom endpoint of
both edges of the helper spike, thus satisfying the invisibility invariant.

###  3.7 Adjusting propagation spikes

Knowing how the corridor is constructed, as described in the previous section,
it is now possible for us to describe how we choose the edges incident at the
propagation corners in the base pockets. Consider a variable segment
$s_{i}=a_{i}b_{i}$ and the associated propagation corner $c_{i}^{s}$, and let
$r_{i}$ be the variable segment in a gadget which is the partner of $s_{i}$;
see Figure 22. We have so far not described exactly how to choose the upper
edge of $\mathcal{P}$ incident at $c_{i}^{s}$, only that it would be a corner
close to $c_{i}^{s}+(1,1)$.

We need our construction to be sufficiently flexible in the sense that for
every value of a variable in $X$, we can construct a cover of triangles that
specifies that value on all variable segments. But recall that each variable
is restricted to a range of length $\delta:=n^{-7}$, where $n$ is the number
of variables in the formula $\Phi$. In our construction, we therefore only
need the flexibility corresponding to a tiny subsegment
$s_{i}^{\prime}=a_{i}^{\prime}b_{i}^{\prime}$ contained in $s_{i}$, and
likewise, we only need to cover a tiny part $r_{i}^{\prime}$ of $r_{i}$, where
$s_{i}^{\prime}$ and $r_{i}^{\prime}$ cover fractions of size just $O(n^{-7})$
of the full segments $s_{i}$ and $r_{i}$. Let $f_{i}^{\prime}$ be the part of
the critical segment $f_{i}$ corresponding to the restricted parts
$(s_{i}^{\prime},r_{i}^{\prime})$. The full critical segment $f_{i}$ has
length $\Theta(1/N^{2})=\Theta(n^{-6})$, so the restricted $f_{i}^{\prime}$
has length $\|f_{i}^{\prime}\|=\Theta(\delta\|f_{i}\|)=\Theta(n^{-13})$.

Let the endpoins of $f_{i}$ and $f_{i}^{\prime}$ be
$\kappa_{0},\kappa_{1},\kappa_{0}^{\prime},\kappa_{1}^{\prime}$, such that
$f_{i}=\kappa_{0}\kappa_{1}$ and
$f^{\prime}_{i}=\kappa_{0}^{\prime}\kappa_{1}^{\prime}$, with $\kappa_{0}$ and
$\kappa_{0}^{\prime}$ to the left. We consider the ray
$\xi:=\overrightarrow{a_{i}^{\prime}d_{0}}$, which passes through the right
endpoint $\kappa_{1}^{\prime}$ of $f_{i}^{\prime}$. Let $e$ be the point on
$\xi$ such that $y(e)=y(\kappa_{1}^{\prime})+1/10CN^{2}$. We now choose the
upper segment incident at $c_{i}^{s}$ such that the extension of the edge
contains the point $e$. We need to argue that with this definition, the
propagation corner $c_{i}^{s}$ can see all points of $f^{\prime}_{i}$, since
then a lever piece can represent any value in the restricted range. For this,
it is enough to see that a triangle contained in $\mathcal{P}$ can cover
$c_{i}$ and all of $f_{i}^{\prime}$. We therefore calculate how large a
portion of $f_{i}$ can be covered by a triangle with a lever edge contained in
$\xi$. The orange triangle $T=c_{i}^{s}ge$ in the figure is the maximal such
piece, and we need to find a lower bound on the length of $T\cap f_{i}$. Let
$F$ be the intersection of $T$ and the line through $g$ parallel to $f_{i}$.
Then $\|F\|=\Theta(1)$. We also have $y(e)-y(g)=\Theta(N^{2})$ and
$y(e)-y(\kappa_{1}^{\prime})=\Theta(1/N^{2})$. Since the parts of $T$ above
$F$ and above $f_{i}$ are similar, we get that $\|T\cap
f_{i}\|=\Theta(N^{-4})=\Theta(n^{-12})$. Since $f_{i}^{\prime}$ has length
$\Theta(n^{-13})$, it follows that $f_{i}^{\prime}\subset T$ when $n$ is large
enough.

Figure 22: Figure showing the principle for choosing the upper incident edge
of the propagation corner $c_{i}^{s}$. The figure is not to scale.

We adjust the edges incident at the lever corners $c_{\sigma}^{r}$ in the
gadgets in a similar way. We can now state the lemma expressing that the
corridor works as intended.

######  Lemma 17.

If the constructed instance $\mathcal{I}_{2}$ has a cover, the following
holds. For $\sigma\in\\{i,j,l\\}$, if $s_{\sigma}$ and $r_{\sigma}$ are both
right-oriented, then
$\mathbf{v}(s_{\sigma},c_{\sigma})\leq\mathbf{v}(r_{\sigma},c_{\sigma}^{r})$.
If both segments are left-oriented, then
$\mathbf{v}(s_{\sigma},c_{\sigma})\geq\mathbf{v}(r_{\sigma},c_{\sigma}^{r})$.

For each $\sigma\in\\{i,j,l\\}$, consider any value $y_{\sigma}\in
I(x_{\sigma})$ in the restricted range of the variable $x_{\sigma}$. There
exists $9$ triangles that cover the lever corners $c_{\sigma}$ and
$c_{\sigma}^{r}$, $\sigma\in\\{i,j,l\\}$, and the helper corners in the
corridor such that the following holds. The triangles cover the $3$ marked
rectangles (containing the restricted critical segments $f^{\prime}_{\sigma}$)
in the corridor and we have
$y_{\sigma}=\mathbf{v}(s_{\sigma},c_{\sigma})=\mathbf{v}(r_{\sigma},c_{\sigma}^{r})$.

###### Proof.

For the first part, for each $\sigma\in\\{i,j,l\\}$, we consider the
restricted critical segment $f^{\prime}_{\sigma}$ in the corridor
corresponding to the pair $(s^{\prime}_{\sigma},r^{\prime}_{\sigma})$. It
follows from Lemma 13 that among all propagation corners in the base pockets,
only the intended corner $c_{\sigma}$ can see $f^{\prime}_{\sigma}$. Likewise,
by Lemma 15, only the corner $c_{\sigma}^{r}$ in the gadget can see
$f^{\prime}_{\sigma}$. Hence, the pieces covering $c_{\sigma}$ and
$c_{\sigma}^{r}$ must together cover $f^{\prime}_{\sigma}$. The statement
therefore follows from Lemma 11.

On the other hand, it follows from the discussion above (in this section) that
for any $y_{\sigma}\in I(x_{\sigma})$ in the restricted range of $x_{\sigma}$,
there are two triangles $T_{0},T_{1}$ covering $c_{\sigma}$ and
$c_{\sigma}^{r}$ that specify the value $y_{\sigma}$ at $s_{\sigma}$ and
$r_{\sigma}$, respectively, and so that $T_{0}$ and $T_{1}$ together cover
$f^{\prime}_{\sigma}$. Using $3$ triangles covering the helper corners in the
corridor, we get a cover for the marked rectangles in the corridor. ∎

###  3.8 The $\geq$-inequality gadget

The $\geq$-inequality gadget is shown in Figure 23. In this gadget, $r_{i}$ is
left-oriented and $r_{j}$ is right-oriented. In addition to the lever corners
$c_{i}^{r}$ and $c_{j}^{r}$, we have a lever corner $c$ which is the left-
responsible for $r_{i}$ and $r_{j}$. Using Observations 6 and 8, we get that
$\mathbf{v}(r_{i},c_{i}^{r})\geq\mathbf{v}(r_{i},c)\geq\mathbf{v}(r_{j},c)\geq\mathbf{v}(r_{j},c_{j}^{r})$.
Recall the bar intersection promise described in Section 2.2. In order to
satisfy this promise, we consider the vertical bar of the marked rectangle of
the restricted range of $r_{i}$ and the horizontal bar of that of $r_{j}$, and
we make the intersection of these two bars a marked rectangle $R_{h}$. We also
make a marked corner $h$ such that $h$ and $R_{h}$ can be covered by a single
piece.

Figure 23: The principle of the $\geq$-inequality gadget. The crosses at the
variable segments $r_{i}$ and $r_{j}$ mark the position of the infinitesimal
restricted range of the segments. The infinitesimal marked rectangle $R_{h}$
is shown as a triangular point, which can be covered by a piece covering the
marked point $h$.

###  3.9 The $\leq$-inequality gadget

The $\leq$-inequality gadget is identical to the $\geq$-inequality gadget,
except that the orientations of the segments $r_{i}$ and $r_{j}$ are swapped.

###  3.10 The $\geq$-addition gadget

In this section we present the construction of the $\geq$-addition gadget
which represents an inequality $x_{i}+x_{j}\geq x_{l}$, where
$i,j,l\in\\{1,\ldots,n\\}$. In Section 3.11 we show how to modify the
construction to obtain the $\leq$-addition gadget for the inequality
$x_{i}+x_{j}\leq x_{l}$. Recall that in Section 3.3, we rewrote all equations
of the form $x_{i}+x_{j}=x_{l}$ in $\Phi$ as two inequalities. We will then
add a gadget for each inequality to our polygon $\mathcal{P}$.

####  3.10.1 Idea behind the gadget construction

The principle behind the gadget follows one from [2]. See Figure 24 (left) for
a sketch of the construction.

######  Lemma 18 ([2]).

For some $v>0$, let $e_{i}:=(v,0),e_{j}:=(-v,0),e_{l}:=(0,0)$. For some
$h\in\mathbb{R}$, let $\ell_{h}$ and $\ell_{2h}$ be the horizontal lines with
$y$-coordinate $-h$ and $-2h$, respectively. Let $\gamma$ be a point with
$y(\gamma)\neq 0$. For $\sigma\in\\{i,j,l\\}$, let
$p_{\sigma}:=\overleftrightarrow{\gamma e_{\sigma}}\cap\ell_{h}$ and
$p^{\prime}_{\sigma}:=\overleftrightarrow{\gamma e_{\sigma}}\cap\ell_{2h}$.
Then $x(p_{l})=\frac{x(p_{i})+x(p_{j})}{2}$ and
$x(p^{\prime}_{l})=x(p_{i})+x(p_{j})$.

Figure 24: Left: The construction described in Lemma 18. The point $e_{l}$ is
at the origin, and then the $x$-coordinate of $p^{\prime}_{l}$ is the sum of
those of $p_{i}$ and $p_{j}$. Right: How we place variable segments on the
lines $\ell_{h}$ and $\ell_{2h}$, and how we use walls of $\mathcal{P}$ to
restrict visibility.

We use the lemma in the following way; see Figure 24 (right). For some value
$w>v+3/2$, we place two variable segments $r^{4}_{i}$ and $r^{2}_{j}$ at the
line $\ell_{h}$, such that the right endpoint of $r^{4}_{i}$ is $(w,-h)$ and
the left endpoint of $r^{2}_{j}$ is $(-w,-h)$.222We use superscripts for
$r^{4}_{i}$ and $r^{2}_{j}$, since we will also have variable segments
$r^{1}_{i},r^{2}_{i},r^{3}_{i}$ and $r^{1}_{j}$ representing the same
variable. More details will be given later. We then place a variable segment
at $r_{l}$ with left endpoint at $(-2,-2h)$. It then follows from the lemma
that if the points $p_{i},p_{j},p^{\prime}_{l}$ are on their respective
segments $r^{4}_{i},r^{2}_{j},r_{l}$, then $p^{\prime}_{l}$ represents a value
which is the sum of those of $p_{i}$ and $p_{j}$ (if the points are not on the
segments, this will still hold if we extrapolate the correspondence between
points and values in the natural way).

Let $\Gamma$ be a collection of points $\gamma$ such that the ray
$\overrightarrow{\gamma e_{i}}$ intersects $r^{4}_{i}$, and the ray
$\overrightarrow{\gamma e_{j}}$ intersects $r^{2}_{j}$. Then $\Gamma$ is a
quadrilateral, bounded by a segment on each of the following rays: the rays
with origin at the endpoints of $r^{4}_{i}$ and containing $e_{i}$, and the
rays with origin at the endpoints of $r_{j}$ and containing $e_{j}$. As shown
in Figure 24 (right), we use walls of $\mathcal{P}$ to create a kind a pivots,
so that we get the following properties.

  * •

For every point $g_{i}$ on $r^{4}_{i}$ and $\gamma$ in $\Gamma$, the points
$\gamma$ and $g_{i}$ can see each other if and only if $\gamma$ is on or to
the right of the line $\overleftrightarrow{g_{i}e_{i}}$.

  * •

For every point $g_{j}$ on $r^{2}_{j}$ and $\gamma$ in $\Gamma$, the points
$\gamma$ and $g_{j}$ can see each other if and only if $\gamma$ is on or to
the right of the line $\overleftrightarrow{g_{j}e_{j}}$.

  * •

For every point $g_{l}$ on $r_{l}$ and $\gamma$ in $\Gamma$, the points
$\gamma$ and $g_{l}$ can see each other if and only if $\gamma$ is on or to
the left of the line $\overleftrightarrow{g_{l}e_{l}}$.

We then get from Lemma 18 that if points $g_{i},g_{j},g_{l}$ on
$r_{i}^{4},r_{j}^{2},r_{j}$, respectively, together see $\Gamma$, then the
value represented by $g_{l}$ is at most the sum of the values represented by
$g_{i}$ and $g_{j}$. We are going to make a marked rectangle around (a
restricted part of) $\Gamma$, which must be covered by pieces covering lever
corners that are responsible for the segments $r_{i}^{4},r_{j}^{2},r_{j}$.

Figure 25: The $\geq$-addition gadget. The gray arrows show the orientations
of the variable segments. Red points are lever corners and blue are pivots.
The crosses mark the infinitesimal restricted ranges on the variable segments,
and the diamond-shaped point in $\Gamma$ is the infinitesimal restricted range
$\Gamma^{\prime}$ of $\Gamma$. Violet regions are lever triangles covering
variable segments representing $x_{i}$, orange represent $x_{j}$, and blue
represent $x_{l}$. The gray dashed rays from lever corners $c_{j}^{r}$ and
$c_{l}^{r}$ show that the corners cannot see $r_{i}^{2}$ and $r_{j}^{2}$,
respectively, so that the bi-cover property is satisfied. The triangular
points indicate the extra marked rectangles we add in order to satisfy the bar
intersection promise. These can be covered by pieces covering the marked
corners $h_{1},h_{2},h_{3},c_{j}^{2},c_{l}^{2}$. For a closeup of the region
in the gray rectangle, see Figure 26.

####  3.10.2 Actual gadget

We use the above principle with values $h:=10.5/CN^{2}$, $v:=5/CN^{2}$, and
$w:=13.5/CN^{2}$. The complete gadget can be seen in Figure 25. As shown in
the figure, we need the variable segments $r_{i}=r_{i}^{1}$ and
$r_{j}=r_{j}^{1}$ to be left-oriented, whereas $r_{l}$ is right-oriented. We
apply sequences of lever mechanisms in order to create the inequalities

$\displaystyle\mathbf{v}(r_{i}^{1},c_{i}^{r})$
$\displaystyle\geq\mathbf{v}(r_{i}^{1},c_{i}^{2})\geq\mathbf{v}(r_{i}^{2},c_{i}^{2})\geq\mathbf{v}(r_{i}^{2},c_{i}^{3})\geq\mathbf{v}(r_{i}^{3},c_{i}^{3})\geq\mathbf{v}(r_{i}^{3},c_{i}^{4})\geq\mathbf{v}(r_{i}^{4},c_{i}^{4})\geq\mathbf{v}(r_{i}^{4},c_{i}^{5}),$
$\displaystyle\mathbf{v}(r_{j}^{1},c_{j}^{r})$
$\displaystyle\geq\mathbf{v}(r_{j}^{1},c_{j}^{2})\geq\mathbf{v}(r_{j}^{2},c_{j}^{2})\geq\mathbf{v}(r_{j}^{2},c_{j}^{3}),\quad\text{and}$
$\displaystyle\mathbf{v}(r_{l},c_{l}^{r})$
$\displaystyle\leq\mathbf{v}(r_{l},c_{l}^{2}).$

Just as we define the instance $\mathcal{I}_{2}$ such that we only need to
cover the infinitesimal restricted ranges of $r_{i}^{4}$, $r_{j}^{2}$, and
$r_{l}$, we also define an infinitesimal restricted region $\Gamma^{\prime}$
of $\Gamma$. We get $\Gamma^{\prime}$ as the intersections of all rays from
the restricted ranges of $r_{i}^{4}$ and $r_{j}^{2}$ through $e_{i}$ and
$e_{j}$, respectively. Thus, $\Gamma^{\prime}$ is a very small quadrilateral
contained in $\Gamma$. We then make the axis-parallel bounding box
$R_{\Gamma^{\prime}}$ a marked rectangle of $\mathcal{I}_{2}$; see the closeup
of the region around $\Gamma$ in Figure 26.

We need the extra variable segments since the segments
$r^{1}_{i},r^{1}_{j},r_{l}$ (that are connected to the base pockets via the
corridor) do not have the right positions to play the roles of the segments
$r_{i}^{4},r_{j}^{2},r_{l}$ described above. For instance, in the case of
$r_{j}^{1}$, the corner $c_{j}^{r}$ is the right-responsible for $r_{j}^{1}$,
so the other responsible corner $c_{j}^{2}$ must be the left-responsible.
However, the corner responsible for covering $r^{2}_{j}$ and part of
$\Gamma^{\prime}$ must be the right-responsible for $r^{2}_{j}$ for the
construction to work as described in Section 3.10.1. Therefore, $r_{j}^{1}$
cannot be used as $r_{j}^{2}$, but this is solved by connecting $r_{j}^{1}$
and $r_{j}^{2}$ by lever mechanisms.

As in the inequality gadgets, Section 3.8 and 3.9, we introduce extra marked
rectangles (denoted as triangles in the figures) to satisfy the bar
intersection promise, and we introduce helper corners that can see them.

To see that the gadget works as intended, suppose that pieces
$Q_{i},Q_{j},Q_{l}$ cover $c_{i}^{5},c_{j}^{3},c_{l}^{2}$, respectively, and
that they together cover $R_{\Gamma^{\prime}}$. Let
$g_{i}:=\mathbf{p}(r_{i}^{4},c_{i}^{5})$,
$g_{j}:=\mathbf{p}(r_{j}^{2},c_{j}^{3})$, and
$g_{l}:=\mathbf{p}(r_{l},c_{l}^{2})$. As $Q_{i},Q_{j},Q_{l}$ cover
$R_{\Gamma^{\prime}}$ and thus $\Gamma^{\prime}$, it follows that
$g_{i},g_{j},g_{l}$ together see $\Gamma^{\prime}$. By the remarks in Section
3.10.1, we then get
$\mathbf{v}(r_{i}^{4},c_{i}^{5})+\mathbf{v}(r_{j}^{2},c_{j}^{3})\geq\mathbf{v}(r_{l},c_{l}^{2})$,
as desired.

Figure 26: Closeup of the region in the gray rectangle from Figure 25. The
pieces $Q_{i},Q_{j},Q_{l}$ cover together the restricted region
$\Gamma^{\prime}$ and also the axis-parallel bounding box $R_{\Gamma}$ of
$\Gamma^{\prime}$.

###  3.11 The $\leq$-addition gadget

We obtain the $\leq$-addition gadget by reversing the orientations of all
variable segments of the $\geq$-addition gadget. Instead of placing $r_{l}$
with the left endpoint at $(-2,-2h)$, we now instead need to place the right
endpoint of $r_{l}$ at the point $(2,-2h)$, so that the scales of the segments
$r_{i}^{4},r_{j}^{2},r_{l}$ match. Recall from Observation 14 that we want the
endpoints of the segments $r_{i}^{1},r_{j}^{1},r_{l}$ (which are connected to
the base pockets via the corridor) to lie on lines with direction $(1,-1)$
with an equidistant horizontal spacing of $13.5/CN^{2}$. Since we move
$r_{l}$, we also adjust $r_{i}^{1}$ and $r_{j}^{1}$ accordingly. The result
can be seen in Figure 27.

Figure 27: The $\leq$-addition gadget.

###  3.12 The $\geq$-inversion gadget

Figure 28: The $\geq$-inversion gadget. To the right is shown a closeup of the
region in the red rectangle.

The principle behind the gadget is similar to one from [2]. The gadget can be
seen in Figure 28. The segments $r_{i}^{1}$ and $r_{j}$ are connected to
segments in the base pockets via a corridor. By the use of lever mechanisms,
we have

$\displaystyle\mathbf{v}(r_{i},c_{i}^{r})$
$\displaystyle\geq\mathbf{v}(r_{i},c_{i}^{2})\geq\mathbf{v}(r_{i}^{2},c_{i}^{2})\geq\mathbf{v}(r_{i}^{2},c_{i}^{3}),\quad\text{and}$
$\displaystyle\mathbf{v}(r_{j},c_{j}^{r})$
$\displaystyle\leq\mathbf{v}(r_{j},c_{j}^{2}).$

The interesting part happens at a critical segment $f_{0}f_{1}$ which
$c_{i}^{3}$ and $c_{j}^{2}$ are responsible for. The pivots of $c_{i}^{3}$ and
$c_{j}^{2}$ are the corners $\xi_{i}$ and $\xi_{j}$, respectively. The
restricted ranges of $r_{i}^{2}$ and $r_{j}$ correspond to an infinitesimal
subsegment $f^{\prime}$ contained in $f_{0}f_{1}$, and we can think of
$f^{\prime}$ as a single point. We have carefully chosen $\xi_{i}$ and
$\xi_{j}$ such that if the pieces covering $c_{i}^{3}$ and $c_{j}^{2}$
together cover $f^{\prime}$, then $\mathbf{v}(r_{i}^{2},c_{i}^{3})\geq
1/\mathbf{v}(r_{j},c_{j}^{2})$, or equivalently,
$\mathbf{v}(r_{i}^{2},c_{i}^{3})\mathbf{v}(r_{j},c_{j}^{2})\geq 1$.

We now specify the coordinates that make this work. The described construction
should be scaled by a factor of $1/CN^{2}$; we avoid mentioning this factor
for the ease of notation. The variable segment $r_{i}^{2}$ has length $3/2$
and left endpoint $(5.5,3)$, and the segment $r_{j}$ also has length $3/2$ and
left endpoint $(14,0)$. We now define
$\xi_{i}:=(9.5,345/34)\approx(9.5,10.15)$ and
$\xi_{j}:=(11.5,51405/3842)\approx(11.5,13.37)$. This defines a critical
segment $f_{0}f_{1}$ with
$f_{0}:=(15961/1438,359835/24446)\approx(11.10,14.72)$ and
$f_{1}:=(8635/754,10281/754)\approx(11.45,13.64)$. We make a helper corner
$h_{2}$ with an incident edge contained in the extension of $f_{0}f_{1}$, so
that a piece covering $h_{2}$ can also cover a region above $f_{0}f_{1}$.
Pieces covering $c_{i}^{3}$, $c_{j}^{2}$, and $h_{2}$ can then together cover
the bounding box of the restricted range $f^{\prime}$ of $f_{0}f_{1}$.

Let $\pi_{i}:r_{i}^{2}\longrightarrow f_{0}f_{1}$ and
$\pi_{j}:f_{0}f_{1}\longrightarrow r_{j}$ be the projections from $r_{i}^{2}$
to $f_{0}f_{1}$, and from $f_{0}f_{1}$ to $r_{j}$, respectively. Consider a
point $p\in r_{i}^{2}$, which can be written as $p=(5+x,3)$ for $x\in[1/2,2]$,
so that $p$ represents the value $x$. Let $\tilde{p}:=\pi_{j}(\pi_{i}(p))$ be
the point on $r_{j}$ corresponding to $p$ on $r_{i}^{2}$. By evaluating the
projections, it is straightforward to check that $\tilde{p}=(16-1/x,0)$.
Hence, $\tilde{p}$ represents the value $1/x$ at $r_{j}$. We now use a similar
argument as in Observation 10. Note that a piece covering $c_{i}^{3}$ and the
point $p$ on $r_{i}^{2}$ can cover only a part of $f_{0}f_{1}$ from
$\pi_{i}(p)$ to $f_{1}$. Hence, the piece $Q_{j}$ covering $c_{j}^{2}$ must
cover the point $\pi_{i}(p)$ on $f_{0}f_{1}$. It then follows that the
rightmost point that $Q_{j}$ can cover of $r_{j}$ is $\pi_{j}(\pi_{i}(p))$.
Hence, $\mathbf{v}(r_{j},c_{j}^{2})\geq 1/x$.

Consider now any cover. We then have $\mathbf{v}(r_{i}^{2},c_{i}^{3})=x$ and
$\mathbf{v}(r_{j},c_{j}^{2})\geq 1/x$, and hence
$\mathbf{v}(r_{i}^{2},c_{i}^{3})\mathbf{v}(r_{j},c_{j}^{2})\geq 1$, as
claimed.

The more complicated fractions appear in the coordinates of $\xi_{i}$ and
$\xi_{j}$ in order to avoid corners with irrational coordinates. When finding
the construction, we made the restriction to coordinates of the forms
$\xi_{i}=(9.5,\chi_{i})$ and $\xi_{j}=(11.5,\chi_{j})$. For any value of
$\chi_{i}$, there is a specific value of $\chi_{j}$ that makes the right
correspondence between $r_{i}^{2}$ and $r_{j}$, but the solution will in
general involve a square root. However, for some exceptional values of
$\chi_{i}$, the interior of the square root is the square of a rational
number, and hence the resulting coordinate of $\xi_{j}$ is rational. We used
Maple to find such a value of $\chi_{i}$.

###  3.13 The $\leq$-inversion gadget

Figure 29: The $\geq$-inversion gadget. For a closeup of the region in the red
rectangle, see Figure 30.  Figure 30: Closeup from Figure 29.

The $\leq$-inversion gadget follows a similar principle as the
$\geq$-inversion gadget, but is in some ways reversed. The gadget can be seen
in Figure 27 with a closeup of an important but small region in Figure 30. The
segments $r_{i}$ and $r_{j}^{1}$ are connected to segments in the base pockets
via the corridor. By the use of lever mechanisms, we have

$\displaystyle\mathbf{v}(r_{i},c_{i}^{r})$
$\displaystyle\geq\mathbf{v}(r_{i},c_{i}^{2}),\quad\text{and}$
$\displaystyle\mathbf{v}(r_{j}^{1},c_{j}^{r})$
$\displaystyle\leq\mathbf{v}(r_{j}^{1},c_{j}^{2})\leq\mathbf{v}(r_{j}^{2},c_{j}^{2})\leq\mathbf{v}(r_{j}^{2},c_{j}^{3}).$

We again have a special critical segment $f_{0}f_{1}$ which $c_{i}^{2}$ and
$c_{j}^{3}$ are responsible for. The pivots of $c_{i}^{2}$ and $c_{j}^{3}$ are
the corners $\xi_{i}$ and $\xi_{j}$, respectively. The restricted ranges of
$r_{i}$ and $r_{j}^{2}$ correspond to an infinitesimal subsegment $f^{\prime}$
contained in $f_{0}f_{1}$, and we can think of $f^{\prime}$ as a single point.
We have carefully chosen $\xi_{i}$ and $\xi_{j}$ such that if the pieces
covering $c_{i}^{2}$ and $c_{j}^{3}$ together cover $f^{\prime}$, then
$\mathbf{v}(r_{i},c_{i}^{2})\leq 1/\mathbf{v}(r_{j}^{2},c_{j}^{3})$, or
equivalently, $\mathbf{v}(r_{i},c_{i}^{2})\mathbf{v}(r_{j}^{2},c_{j}^{3})\leq
1$.

We now specify the coordinates that make this work. We again leave out a
factor of $1/CN^{2}$ in the coordinates for the ease of notation. The variable
segment $r_{i}$ has length $3/2$ and left endpoint $(0.5,0)$, and the segment
$r_{j}^{2}$ also has length $3/2$ and left endpoint $(17.5,2)$. We now define
$\xi_{i}:=(5,57/16)\approx(5,3.56)$ and $\xi_{j}:=(7,1041/208)\approx(7,5)$.
This defines a critical segment $f_{0}f_{1}$ with
$f_{0}:=(235/37,3059/592)\approx(6.35,5.17)$ and
$f_{1}:=(735/107,25897/5136)\approx(6.87,5.04)$. We make a helper corner $h$
with an incident edge contained in the extension of $f_{0}f_{1}$, so that a
piece covering $h$ can also cover a region below $f_{0}f_{1}$. Pieces covering
$c_{i}^{2}$, $c_{j}^{3}$, and $h$ can then together cover the bounding box of
the restricted range $f^{\prime}$ of $f_{0}f_{1}$. A piece covering $h$ can
likewise cover a marked rectangle that is introduced in order to satisfy the
bar intersection promise.

As in the $\geq$-inequality gadget, it now follows that
$\mathbf{v}(r_{i}^{2},c_{i}^{3})\mathbf{v}(r_{j},c_{j}^{2})\leq 1$.

###  3.14 Putting it all together

Let us now summarize the entire construction. We consider an instance
$\mathcal{I}_{1}$ of Range-Etr-Inv with $n$ variables and a formula $\Phi$
consisting of addition and inversion constraints. We rewrite $\Phi$ as a
formula $\Phi_{\text{ineq}}$, which is a conjunction of inequalities among
$3n$ variables $X_{\text{ineq}}:=\\{x_{1},\ldots,x_{3n}\\}$, as described in
Section 3.3. We make a base pocket for each variable $x_{i}\in
X_{\text{ineq}}$ and a variable segment in this base pocket for each
occurrence of $x_{i}$ in an inequality in $\Phi_{\text{ineq}}$. We then make a
gadget for each inequality, as described in Sections 3.8–3.13. The gadgets are
connected to the base pockets by corridors, as described in Section 3.6, which
ensures that the values represented in the gadgets satisfy appropriate
inequalities compared to those in the base pockets.

Suppose that the constructed instance $\mathcal{I}_{2}$ has a cover. By the
correctness of the corridor, Lemma 17, we have inequalities between the values
in the base pockets and in the gadgets as intended. As described in Section
3.4, the use of the $\geq$\- and $\leq$-inequality gadgets ensure that the
variables in the base pockets are represented consistently. By the correctness
of the addition and inversion gadgets, Sections 3.10–3.13, we then get that
the values specified on the variable segments correspond to a solution to
$\Phi$.

On the other hand, given a solution to $\Phi$, we get a corresponding cover
for $\mathcal{I}_{2}$ using only maximal triangles in the following way. For
each variable segment $s$ and each lever corner $c$ responsible for $s$, we
use a triangular piece with a corner at $c$ and two edges that are extensions
of the edges of $\mathcal{P}$ incident at $c$. The last edge is chosen so that
at $s$, the triangle represents the value specified by the solution to $\Phi$.
These triangles together cover all variable segments and also the remaining
(non-horizontal) critical segments. By adding triangles that cover the helper
corners, we can make a cover for all marked rectangles. It is also clear that
the instance $\mathcal{I}_{2}$ can be constructed from $\mathcal{I}_{1}$ in
polynomial time. We have therefore proved Theorem 7 and in particular that
MRCC is $\exists\mathbb{R}$-complete.

In order to use Lemma 5 to prove that the original problem MCC is also
$\exists\mathbb{R}$-complete, we need the constructed instance
$\mathcal{I}_{2}$ to satisfy the promise of MRCC-instances, described in
Section 2.2. It is straightforward to verify the skew triangle promise.
Regarding the trapezoid generality promise, it is sufficient that no two
corners are visible and have the same $x$\- or $y$-coordinate. This is not
true for the construction as described: The corners next to the propagation
corners in a base pocket are mutually visible and on a vertical line. Likewise
are the corners of the left doors of the corridors. However, it is easy to see
that all these corners can be slightly moved, say, by a distance of
$\Theta(1/N^{3})$, without affecting the correctness of the construction, and
then the promise will be satisfied.

For the bar intersection promise, we note that a bar from marked rectangles in
a base pocket cannot intersect bars from other base pockets or corridors or
gadgets. Likewise, bars in corridors cannot intersect bars from other
corridors, base pockets or gadgets. In the sections describing the individual
components (base pockets, corridors, gadgets), we have been careful to satisfy
the bar intersection promise within that component. It is therefore also
satisfied globally. Finally, for the broad cover property, suppose that
$\mathcal{I}_{2}$ has a cover $\mathcal{Q}$. We then have a solution to
$\Phi$, as described above. This solution corresponds to a cover
$\mathcal{Q}^{\prime}$ for $\mathcal{I}_{2}$ using only triangles, and for
each marked corner $c$, the triangle $T$ covering $c$ has edges that are
extensions of the edges of $\mathcal{P}$ incident at $c$. Hence,
$\Delta(c)\subset T$, as needed.

Since we have verified that the instance $\mathcal{I}_{2}$ can be assumed to
satisfy the promise, we then get from Lemma 5 that MCC is
$\exists\mathbb{R}$-complete. We now observe that if there exists a cover of
the resulting instance $\mathcal{I}^{\prime}_{2}$ of MCC, then there also
exists a cover consisting of triangles only: As we have seen before, there
exists a triangle cover for the instance $\mathcal{I}_{2}$ of MRCC. It is
described in the proof of Lemma 5 how we can then get a cover for
$\mathcal{I}_{2}^{\prime}$ by covering the added spikes and remaining parts of
the polygon with triangles. Therefore, we also get
$\exists\mathbb{R}$-completeness of Minimum Triangle Cover. We have then
proved Theorem 1, repeated here.

See 1

We can now also prove Corollary 2.

See 2

###### Proof.

Let $\Phi=\Phi(x)$ be the Etr-formula $x\cdot x\cdot x\cdot x\cdot x-x-x-
x-x+1+1=0$, i.e., the equation $x^{5}-4x+2=0$ written up in the way required
for an Etr-formula. As mentioned, the equation is known to have a single real
solution $x=y$ for a number $y\in\mathbb{R}$ which is not expressible by
radicals [6]. We reduce $\Phi$ to an instance $\mathcal{I}_{1}$ of Range-Etr-
Inv using the reduction from [3], which can then be reduced to an instance
$\langle\mathcal{P},k\rangle$ of MCC using the reductions described in this
paper. By looking at the reduction from [3], one sees that one of the
variables $x^{\prime}$ in $\mathcal{I}_{1}$ corresponds to $x$ in the formula
$\Phi$, in the sense that $x^{\prime}=q_{1}x+q_{2}$ for two fixed rationals
$q_{1},q_{2}\in\mathbb{Q}$. Hence, in all solutions to $\mathcal{I}_{1}$,
$x^{\prime}$ has a value $y^{\prime}\in\mathbb{R}$ that is not expressible by
radicals. Consider a variable segment $s$ in $\mathcal{P}$ that represents
$x^{\prime}$, and let $c$ be a lever corner responsible for $s$ and $Q$ a
piece covering $c$ in a cover for $\mathcal{P}$. We then have
$\mathbf{v}(s,c)=y^{\prime}$. Let $e_{1}e_{2}$ be the edge of $Q$ that
intersects $s$ and thus defines this value $y^{\prime}$. If the corners
$e_{1}$ and $e_{2}$ of $Q$ had coordinates expressible by radicals, then so
would the intersection point of $e_{1}e_{2}$ with $s$, as the endpoints of $s$
are rational, and then the represented value would be expressible by radicals
as well. Therefore, $e_{1}$ or $e_{2}$ has a coordinate that is not
expressible by radicals. ∎

##  4 Concluding remarks

As described, the polygon produced by our reduction has some triples of
collinear corners. We here outline how it can be changed to avoid this. The
proof of Lemma 5 describes the transformation from an instance
$\mathcal{I}_{2}$ of MRCC to an instance $\mathcal{I}^{\prime}_{2}$ of MCC by
adding some spikes to the polygon. The spikes can be covered by one triangle
each, such that these triangles also cover everything outside the marked
rectangles and the triangles $\Delta(c)$ for each marked corner $c$. The
spikes introduce some collinear points of two types: (i) The way we originally
drew the spikes in Figures 4 and 5, two different spikes may have edges
contained in the same line, creating four collinear corners. (ii)
Additionally, some spikes may have a horizontal or vertical edge that also
contains a corner of the original polygon.

In order to eliminate these collinear corners, we do as follows. For each
critical segment $s$, we consider the marked rectangle $R$ containing $s$. We
now make sure that $s$ is disjoint from the boundary of $R$. If $s$ intersects
the boundary $\partial R$, we make $R$ a tiny bit larger so that $s$ is
contained in the interior; see Figure 31. If $s$ is a variable segment, then
$s$ would originally be contained in the top or bottom edge of $R$, so when
enlarging $R$, we also need to introduce a new helper corner that can cover
the part of $R$ on one side of $s$, as the pieces covering the corners
responsible for $s$ are only covering the other side of $s$. With this
modification, we again obtain that the instance with enlarged rectangles has a
cover if and only if $\Phi$ has a solution.

Figure 31: Instead of the marked rectangle $R$ where $s$ is contained in the
bottom segment, we use the slightly larger $R^{\prime}$ where $s$ is in the
interior. We then add the helper spike with a corner $c_{h}$ that can cover
the part of $R^{\prime}$ below $s$.

When reducing to MCC and creating the instance $\mathcal{I}^{\prime}_{2}$, we
now enlarge the spikes a bit, as shown in Figure 32, which eliminates both
collinearities of types (i) and (ii). We have kept the property that no piece
in a cover for $\mathcal{I}_{2}^{\prime}$ can cover two spikes, so there must
be a piece for each spike in a cover for $\mathcal{I}_{2}^{\prime}$. It is now
conceivable that a piece covering a spike can also cover a part of a marked
rectangle, but by changing the spikes sufficiently little, the covered part of
the rectangle is very close to the boundary, leaving the critical segment
inside to be covered by the responsible marked corners. Hence, the reduction
still works as intended.

Figure 32: Enlarging spikes to avoid collinear points. Note that the resulting
spike corners $a$ and $b$ do not see each other.

An interesting question that remains open is to determine the complexity of
covering a simple polygon with a minimum number of spiral polygons.

## Acknowledgements

I thank Aurélien Ooms for useful discussions in the initial phases of this
work, and Joseph O’Rourke for sending me his paper [36].

## References

  * [1] Zachary Abel, Erik D. Demaine, Martin L. Demaine, Sarah Eisenstat, Jayson Lynch and Tao B. Schardl  “Who Needs Crossings? Hardness of Plane Graph Rigidity”  In _32nd International Symposium on Computational Geometry (SoCG 2016)_ , 2016, pp. 3:1–3:15  DOI: 10.4230/LIPIcs.SoCG.2016.3
  * [2] Mikkel Abrahamsen, Anna Adamaszek and Tillmann Miltzow  “The Art Gallery Problem is $\exists\mathbb{R}$-Complete” To appear. Preliminary versions presented at STOC 2018 and SoCG 2017.  In _Journal of the ACM_ , 2021
  * [3] Mikkel Abrahamsen, Tillmann Miltzow and Nadja Seiferth  “Framework for $\exists\mathbb{R}$-Completeness of Two-Dimensional Packing Problems”  In _61st IEEE Annual Symposium on Foundations of Computer Science (FOCS 2020)_ , 2020  DOI: 10.1109/FOCS46700.2020.00098
  * [4] Alok Aggarwal  “The art gallery theorem: Its variations, applications and algorithmic aspects”, 1984
  * [5] Shmuel Asafi, Avi Goren and Daniel Cohen-Or  “Weak Convex Decomposition by Lines-of-sight”  In _Computer Graphics Forum_ 32.5, 2013, pp. 23–31  DOI: 10.1111/cgf.12169
  * [6] Julio R. Bastida and Roger Lyndon  “Field Extensions and Galois Theory”, Encyclopedia of Mathematics and its Applications  Cambridge University Press, 1984  DOI: 10.1017/CBO9781107340749