We show that many natural two-dimensional packing problems are algorithmically equivalent to finding real roots of multivariate polynomials.
A two-dimensional packing problem is defined by the type of pieces, containers, and motions  that are allowed.
The aim is to decide if a given set of pieces can be placed inside a given container.
The pieces must be placed so that in the resulting placement, they are pairwise interior-disjoint, and only motions of the allowed type can be used to move them there.
We establish a framework which enables us to show that for many combinations of allowed pieces, containers, and motions, the resulting problem is $\ER$-complete.
This means that the problem is equivalent (under polynomial time reductions) to deciding whether a given system of polynomial equations and inequalities with integer coefficients has a real solution.

We consider packing problems where only translations are allowed as the motions, and problems where arbitrary rigid motions are allowed, i.e., both translations and rotations.
When rotations are allowed, we show that the following combinations of allowed pieces and containers result in $\ER$-complete problems:

* simple polygons, each of which has at most $8$ corners, into a square,

* convex objects bounded by line segments and hyperbolic curves into a square,

* convex polygons into a container bounded by line segments and hyperbolic curves.

Restricted to translations, we show that the problems for the following combinations are $\ER$-complete:

* objects bounded by segments and hyperbolic curves into a square,

* convex polygons into a container bounded by segments and hyperbolic curves.

Two-dimensional packing problems are an active field of research both in computational geometry and operations research.
The problems are very important in many industries and processes such as clothing production, sheet metal cutting, shipping, and 3D printing.
Our results give an explanation for the lack of exact algorithms, as it follows that many natural attempts to discretize the problems have inherent shortcomings.

In practice, packing problems are solved with heuristics.
This work explains why methods guaranteed to produce optimal solutions for problems in NP, like SAT- or IP-solvers, are not applicable without additional assumptions, unless $\ER=\NP$.

§ INTRODUCTION

Packing problems are everywhere in our daily lives.
To give a few examples, you solve packing problems when deciding where to put your furniture in your home, the manufacturer of your clothing arranges cutting patterns on a large piece of fabric in order to minimize waste, and at Christmas time you are trying to cut out as many cookies from a dough as you can.
In a large number of industries, it is crucial to solve complicated instances of packing problems efficiently.
In addition to clothing manufacturing, we mention leather, glass, wood, and sheet metal cutting, selective laser sintering, shipping (packing goods in containers), and 3D printing (arranging the parts to be printed in the printing volume); see Figure <ref>.

Real examples of nesting on a leather hide (left) and a piece of fabric (right), kindly provided by MIRISYS and produced by their software for automatic nesting, <https://www.mirisys.com/>.

Packing problems can be easily and precisely defined
in a mathematical manner, but many important questions are still completely elusive.
In this work, we uncover a
fundamental aspect of many versions of geometric packing by settling their computational difficulty.

We denote as the packing problem
with pieces of the type , containers
of type $\conttype$, and motions of type $\motiontype$.
In an instance of , we are
given pieces $p_1,\ldots,p_n$ of type $\piecetype$ and a container $\cont$ of type $\conttype$.
We want to decide if there is a motion of type $\motiontype$ for each piece such that after moving the pieces by these motions, each piece is in $\cont$ and the pieces are pairwise interior-disjoint.
Such a placement of the pieces is called a valid placement.

As the allowed motions, we consider translations () and rigid motions (), where a rigid motion is a combination of a translation and a rotation.
As containers and pieces, we consider squares ($\square$), convex polygons (), simple polygons (), convex curved polygons (), and curved polygons (), where a curved polygon is a region enclosed by a simple closed curve consisting of a finite number of line segments and arcs contained in hyperbolae (such as the graph of $y=1/x$).

The problems with only translations allowed are relevant to some industries; for instance when arranging cutting patterns on a roll of fabric for clothing production, where the orientation of each piece has to follow the orientation of the weaving or a pattern printed on the fabric.
In other contexts such as leather, glass, or sheet metal cutting, there are usually no such restrictions, so rotations can be used to minimize waste.
As can be seen from Figure <ref>, it is relevant to study packing problems where the pieces as well as the containers may be non-convex and have boundaries consisting of many types of curves (not just straight line segments).

We show that many of the above mentioned variants of packing are $\ER$-complete.
The complexity class $\ER$ will be defined below.
We call our developed techniques a framework, since the same techniques turn out to be applicable to prove hardness for many versions of packing.
With adjustments or additions, they can likely be used for other versions or proofs of other types of hardness as well.

*The Existential Theory of the Reals.
An formula is a formula of the form

\[\exists x_1,\ldots,x_n\; \Phi(x_1,\ldots,x_n),\]

where $\Phi$ is a well-formed formula over the alphabet $\{0,1,x_1,\ldots, x_n, +, \cdot, =, \leq , < , \land
, \lor, \lnot\}$.
The problem is to decide whether a given formula is true.
This leads to the complexity class Existential Theory of the Reals (),
which consists of all those problems that are
many-one reducible to in polynomial time.
The term Existential Theory of the Reals refers
ambiguously to a formal language,
a corresponding algorithmic problem (), and a complexity class ($\ER$).
Let us start with the formal logic.
\[\Sigma \mydef \{\forall, \exists, 0,1,x_1,\ldots, x_n, +, \cdot, =, \leq , < , \land
, \lor, \lnot\} \]
be an alphabet for some $n\geq 1$.
A sentence over $\Sigma$ is a well-formed formula with no free variables, i.e., so that every variable is bound to a quantifier.
The Existential Theory of the Reals is the true sentences of the form

\[\exists x_1,\ldots,x_n\; \Phi(x_1,\ldots,x_n),\]

where $\Phi$ is a quantifier-free formula.
The algorithmic problem is to decide whether a sentence of this form is true or not.
At last, this leads us to the complexity class Existential Theory of the Reals (),
which consists of all those languages that are
many-one reducible to in polynomial time.
Given a quantifier-free formula $\Phi$, we define
the solution space of $\Phi$ as
$V(\Phi) \mydef \{\mathbf x\in\R^n : \Phi(\mathbf x)\}$.
Thus in other words, is to decide
if $V(\Phi)$ is empty or not.
It is currently known that

\begin{align}
\label{eq:inclusions}
\NP \subseteq \ER \subseteq \PSPACE .
\end{align}

To show the first inclusion is an easy exercise, whereas the second is non-trivial and was first proven by Canny <cit.>.
A problem $P$ is $\ER$-hard if $\ETR$ is many-one reducible to $P$ in polynomial time, and $P$ is $\ER$-complete if $P$ is $\ER$-hard and in $\ER$. [There seems to be no general convention about how to pronounce terms such as $\ER$-complete.
We propose to use the pronunciation E-T-R-complete.] None of the inclusions (<ref>) are known to be strict, but the first is widely believed to be <cit.>, implying that the $\ER$-hard problems are not in NP.
As examples of -complete problems, we mention problems related to realization of order-types <cit.>, graph drawing <cit.>, recognition of geometric graphs <cit.>, straightening of curves <cit.>,
the art gallery problem <cit.>,
Nash-equilibria <cit.>,
linkages <cit.>,
matrix-decompositions <cit.>,
polytope theory <cit.>.
See also the surveys <cit.>.

Showing that the packing problems we are dealing with in this paper are contained in is easy using the following recent result.
[Erickson, Hoog, Miltzow <cit.>]
For any decision problem $P$, there is a real verification algorithm for $P$ if
and only if $P \in \ER$.

A real verification algorithm is like a verification algorithm for a problem in NP with the additional feature that it accepts real inputs for the witness and runs on the real RAM.
(We refer to <cit.> for the full definition, as it is too long to include here.)

Thus in order to show that our packing problems lie in , we have to specify a witness and a real verification algorithm.
The witness is simply the motions that move the pieces to a valid placement.
The verification algorithm checks that the pieces are pairwise interior-disjoint and contained in the container.
Note that without the theorem above, we would need to describe an -formula equivalent to a given packing instance in order to show -membership.
Although this is not difficult for packing, it would still require some work.

This table displays $12$ variants of the
packing problem with rotations and translations, and $12$ with translations only.
$\ER$ means $\ER$-complete and NP means NP-complete.
We show that $16$ of the problems are
The problems marked with * are the basic problems.
The $\ER$-completeness of the remaining problems follow since there is a basic problem in the table which is more restricted.
The complexities of the four variants marked with ? remain elusive.

We show that various two-dimensional
packing problems are -complete.
A compact overview of our results is displayed in Table <ref>.
In the table, the second row (with problems ) is in some sense redundant, since the $\ER$-completeness results can be deduced from the more restricted third row (the problems □).
We anyway include the row since a majority of our reduction is to establish hardness of problems with polygonal containers, and only later we reduce these problems to the case where the container is a square.
For the green cells, we have constructions that work both with and without rotations allowed; for instance, we can use the same reduction to as to .
For the orange cells, the reductions only work when rotations are allowed.

A strength of our reductions is that in the resulting constructions, all corners can be described with rational coordinates that require a number of bits only logarithmic in the total number of bits used to represent the instance.
Therefore, we show that the problems are strongly $\ER$-hard.
Another strength is that all the pieces
have constant complexity, i.e., each piece can be described by its boundary as a union of $O(1)$ straight line segments and arcs contained in hyperbolae.

It is folklore that the problems in the blue cells, i.e., the problems with polygonal pieces and containers and only translations allowed, are in $\NP$, see Section <ref> for a sketch of a proof.

It is folklore that the problems in the blue cells, i.e., the problems with polygonal pieces and containers and only translations allowed, are in $\NP$, and in the following we sketch an argument why.
We show that a valid placement can be specified as the translations of the pieces represented by a number of bits polynomial in the input size.
Consider a valid placement of the pieces.
For each pair of a segment $s$ and a corner $c$ (each of a piece or the container), we consider the line $\ell(s)$ containing $s$ and note which of the closed half-planes bounded by $\ell(s)$ contains $c$.
Then we build a linear program (LP) using that information in the natural way.
Here, the translation of each piece is described by two variables and for each pair $(s,c)$, we have one constraint involving at most four variables, enforcing $c$ to be on the correct side of $\ell(s)$.
It is easy to verify that the constraint is linear.
The solution of the LP gives a valid placement of every piece and as the LP is polynomial in the input, so is the number of the bits of the solution to the LP.
Note that if rotations are included, the corresponding constraints become non-linear.

To sum up, we conclude that two distinct features are key for -hardness of packing problems: Rotations and non-polygonal shapes.
The results provide evidence that many packing problems
are likely harder than problems in .
This gives a confirmation to the operations research community that they cannot employ standard algorithm techniques (solvers for IP and SAT, etc.) that work well for many NP-complete problems like scheduling, TSP, and SAT.
The main message for the theory community is that dealing with rotations or non-polygonal shapes can probably only be done if we relax the problem considerably.

An important step in the proof of -hardness of the art gallery problem <cit.> was the introduction of formulae.

An 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
$x+y=z$ and $x\cdot y=1$

\begin{align*}
x+y=z,\quad x\cdot y=1
\end{align*}

for $x,y,z \in \{x_1, \ldots, x_n\}$.

It was proven to be -complete to decide if a given formula $\Phi$ has a solution <cit.>.
This has since then been used to prove -completeness of a geometric graph drawing problem with prescribed face areas <cit.>, completing a partially (straight-line) drawn  graph <cit.>, and the polytope nesting problem <cit.>.
In this paper, we introduce the following promise problem which we prove is -complete.

An instance $\I=\left[\Phi,\delta,(I(x_1),\ldots,I(x_n))\right]$ of the problem consists of an formula $\Phi$, a number $\delta\mydef 2^{-l}$ for a positive integer $l$, and, for each variable $x\in\{x_1,\ldots,x_n\}$, an interval $I(x)\subseteq [1/2,2]$ such that $|I(x)|\leq 2 \delta$.
For every inversion constraint $x\cdot y=1$, we have either $I(x)=I(y) = [1-\delta,1+\delta]$ or $I(x)=[2/3-\delta,2/3+\delta]$ and $I(y)=[3/2-\delta,3/2+\delta]$.
We are promised that $V(\Phi)\subset I(x_1)\times\cdots\times I(x_n)$.
The goal is to decide whether $V(\Phi)\neq\emptyset$.

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

The promise that we only need to look for solutions to an formula in some tiny ranges of the variables will be crucial in our reduction.

Related work.
Most papers on geometric packing problems
theoretical computer science allow translations only despite the high relevance of problems with rotations allowed.
One line of research deals with packing axis-parallel rectangles into an axis-parallel rectangle with translations only
Most often an optimization version is studied where the rectangles also get weights
and the aim is to maximize the total weight
of the packed rectangles, in which case the problem is called
$2$-dimensional knapsack.
The current best approximation factor is $1.89$
using involved geometric arguments based on the idea
to use an $L$-shaped layout <cit.>.
There exists also a QPTAS <cit.>.

Another line of research deals with strip-packing, where we are given a set of pieces that have to be placed inside a strip of a certain width in an axis-parallel fashion <cit.>.
Rotations by $90$ degrees are sometimes allowed.
The aim is to minimize the total height.
The best polynomial time approximation algorithm has approximation ratio $5/3+\eps$ <cit.>, whereas the best pseudopolynomial time algorithm achieves an approximation ratio of $5/4+\eps$ <cit.> and
this is best possible <cit.>.

Several other packing variants are known (or believed) to be NP-hard (some of the sources still lack detailed journal versions).
Here we mention the problem of packing squares into a square by translation
<cit.>,  packing segments into a simple polygon by translation
<cit.>, and packing circles into a square
Alt <cit.> proves by a simple reduction from the partition problem that packing rectangles into a rectangle is NP-hard, and this reduction works with and without rotations allowed (note that a priory, it is not clear that rotations make problems more difficult, and it is straightforward to define (artificial) problems that even get easer with rotations).
It is easy to modify the reduction to the problem of packing rectangles into a square, so this implies NP-hardness of all problems in Table <ref>.

Left: The optimal packing of five unit squares already requires rotations. Right: The currently best known packing of eleven unit squares into a larger square <cit.>.

A fundamental problem related to packing is to find the smallest square containing a given number of unit squares, with rotations allowed.
A long line of mathematical research has been devoted to this problem, initiated by Erdős and Graham <cit.> in 1975, and it is still an active research area <cit.>.
Already with five unit squares, rotations are needed in the optimal solution:
For eleven, the exact answer is unknown <cit.> and the current best solution is .
Even for eleven unit squares, the exact answer is unknown <cit.>; see Figure <ref>.
Other packing problems have much older roots, for instance Kepler's conjecture on the densest packings of spheres from 1611, famously proven by Hales in 2005 <cit.>.
The 2D analog, i.e., finding the densest packings of unit disks, was solved already in 1773 by Joseph Louis Lagrange under the assumption that the disk configurations are lattices, and the general case was solved by László Fejes Tóth in 1940 <cit.> (Axel Thue already published a proof in 1890 which is considered incomplete).

There is a staggering amount of papers in operations research on packing problems.
The research is mainly experimental and focuses on the development of heuristics to solve benchmark instances efficiently.
We refer to some surveys for an overview <cit.>.
In contrary to theoretical work, there is a lot of experimental work on packing pieces with irregular shapes and with arbitrary rotations allowed.

§ REDUCTION SKELETON

In this section, we give an overview of the steps and concepts needed in our reductions.
The rest of the paper will then fill out the details.

and .
In Section <ref>, we prove Theorem <ref>, namely that the problem (recall Definition <ref>) is -complete.
We also define an extension of the problem called , which we also prove to be -complete.
An instance of is an instance of together with a graphical representation of the formula $\Phi$, i.e., a drawing of $\Phi$ of a specific form, which we call a wiring diagram; see Figure <ref> for an example.
In the following, we outline the properties of a wiring diagram and refer to Section <ref> for the details.

In a wiring diagram, each variable $x_i$ of $\Phi$, $i\in\{1,\ldots,n\}$, is represented by two $x$-monotone polygonal curves $\overrightarrow{x_i}$ and $\overleftarrow{x_i}$, which we call wires.
The wires consist of segments contained in a set of $2n$ equidistant horizontal lines $\ell_1,\ldots,\ell_{2n}$ and jump segments with endpoints on neighbouring lines $\ell_j,\ell_{j+1}$.
The wires are disjoint except that each jump segment must cross another jump segment.
It is important that the two wires $\overrightarrow{x_i},\overleftarrow{x_i}$ representing $x_i$ start and end on the neighbouring lines $\ell_{2i-1},\ell_{2i}$, respectively.
We represent each constraint of $\Phi$ as two inequalities, i.e., $x_i+x_j=x_k$ becomes $x_i+x_j\leq x_k$ and $x_i+x_j\geq x_k$ and $x_i\cdot x_j=1$ becomes $x_i\cdot x_j\leq 1$ and $x_i\cdot x_j\geq 1$.
Each inequality is represented by an axis-parallel constraint box intersecting the three or two topmost diagram lines; three for addition constraints and two for inversion constraints.

A wiring diagram corresponding to the formula $x_2+x_3=x_1\land x_1\cdot x_2=1$.

Overview of geometric construction.
Let an instance $\I$ of be given with formula $\Phi$ of variables $x_1,\ldots,x_n$ and $\delta\mydef n^{-300}$.
We are going to construct an instance of a packing problem with $N=O(n^4)$ pieces, since this will be the complexity of the size of the wiring diagram of $\I$.
The general idea is to build a packing instance on top of the wiring diagram.
We define a polygonal container $\cont\mydef \cont(\mathcal I)$ containing the wiring diagram in the interior, and a set of pieces $\p$ to be placed in $\cont$.
The container $\cont$ is bounded from below by a line segment, from left and right by $y$-monotone chains, and from above by an $x$-monotone chain.
See Figure <ref> for a sketch of a complete example.

In Sections <ref>–<ref>, we present reductions to the variants of the packing problem of the forms and , i.e., where the container is a polygon or a curved polygon.
Section <ref> describes a reduction to the cases where the container is a square.
This might however change the type of pieces: applying the reduction to a problem of the type for $\piecetype\in\{\convexpolygon,\polygon,\convexcurved\}$ results in a problem of the type □, since pieces of type $\curved$ will be added during the construction.

Defining the construction in steps from left to right.
We define the packing instance as we sweep over the wiring diagram of $\I$ with a vertical sweep line from left to right.
Each step corresponds to one of the following events of the wiring diagram as we sweep over it from left to right:
(1) the introduction of a pair of wires $(\overrightarrow{x_i},\overleftarrow{x_i})$, (2) a crossing of two wires, (3) an addition or inversion constraint, (4) the termination of a pair of wires $(\overrightarrow{x_i},\overleftarrow{x_i})$.

* the introduction of a pair of wires $(\overrightarrow{x_i},\overleftarrow{x_i})$,

* a crossing of two wires,

* an addition or inversion constraint,

* the termination of a pair of wires $(\overrightarrow{x_i},\overleftarrow{x_i})$.

In each step, we add one or more gadgets, each involving a constant number of pieces and possibly a constant number of edges to the boundary of the container $\cont$.
When the sweep line passes over the right endpoints of the last wires $(\overrightarrow{x_n},\overleftarrow{x_n})$, the complete construction of the container $\cont$ and all the pieces $\p$ has been done.

The overall goal of the construction is to prove the following theorem.

Let $\cont$ be the container and be the pieces of an instance of or that we construct based on the instance $\I$ of ,
using the gadgets from Section <ref> and Section <ref>.
Then $\I$ has a solution if and only if there is a valid placement of $\p$ in $\cont$.

From Theorem <ref>, we now get the claimed results of row one and two in Table <ref>.

The problems , , , and are -hard.

The third row in Table <ref> follows from the reduction in Section <ref>, as described later in this section.

Variable pieces.
Each variable $x$ of $\Phi$ will be represented by a number of variable pieces in our construction, each of which is a convex polygon.
Each variable piece represents exactly one variable $x$, and we make a correspondance between certain placements of the piece and the values of $x$.
Recall that $x$ comes with an interval $I(x)\subset [1/2,2]$, which we can write as $I(x)=[m-w,m+w]$ for $w\leq\delta$.
When adding a variable piece to our construction, we also specify the middle placement of the piece, which is a specific placement where it encodes the value $m$ of $x$.
In the middle placement, the piece will have a pair of (long) horizontal edges which have distance $10$.
By sliding the piece to the left or to the right from the middle placement, we obtain placements of the piece that encode all real values of $x$, even values outside the range $[1/2,2]$.
Each variable piece will be defined to be either right- or left-oriented.
By sliding a right-oriented (resp. left-oriented) variable piece to the right by some amount $t\geq 0$, we obtain a placement that encodes the value $m+t$ (resp. $m-t$), while sliding it to the left by $t$ results in a placement encoding $m-t$ (resp. $m+t$).
If the piece is rotated in a different way or placed higher or lower than the middle placement, we do not define any value of $x$ to be encoded by the placement.
We define the canonical placements of a variable piece to be the placements that encode values in the interval $I(x)$; see Figure <ref>.

On each wire $\overrightarrow{x_i}$ or $\overleftarrow{x_i}$
in the wiring diagram of $\I$, we will place some variable pieces representing $x_i$.
The pieces placed on one wire are called a lane.
The variable pieces on $\overrightarrow{x_i}$ and $\overleftarrow{x_i}$ are oriented to right and left, respectively.
We also introduce some variable pieces which will be placed at other places than on the wires, namely above the topmost wire where they will be introduced in the steps of the construction corresponding to addition or inversion constraints.

A wire $\protect\overrightarrow x$ and a variable piece representing $x$ placed on top, showing the leftmost and rightmost canonical placements of the piece.
The large arrow in the piece indicates that the piece is right-oriented.

Sketches of some of the gadgets can be seen in Figure <ref>.
In the wiring diagram, each variable $x_i$ is represented by two wires $\overrightarrow{x_i}$ and $\overleftarrow{x_i}$ such that the left endpoints of $\overrightarrow{x_i}$ and $\overleftarrow{x_i}$ are vertically aligned at distance $10$, as are the right endpoints.
In each end of the wires, we build an anchor (Section <ref>) which ensures that the pieces placed on $\overrightarrow{x_i}$ and those placed on $\overleftarrow{x_i}$ encode the value of $x_i$ consistently.

Whenever two wires cross, we build a swap (Section <ref>).
The swap employs a central piece that can translate in all directions, so that when it is pushed by a variable piece, the push will propagate to the neighbouring variable piece on the other side of the crossing.
We describe adders (Section <ref>) to implement the addition constraints and inversion gadgets (Section <ref>) for the inversion constraints.
We describe several different inversion gadgets (see Figure <ref> (d–f)), and which versions we use depends on the variant of packing we are reducing to.

Every time we add a gadget to the construction, we also introduce a constant number of new pieces.
Each variable piece is introduced in one gadget where the left end of the piece is defined.
The piece then extends outside the gadget to the right and the right end of the piece will be defined in another gadget added later to the construction.
The piece is exiting the former gadget and entering the latter.
In between the left and right end of the piece, defined in these two gadgets, the piece is bounded by a pair of horizontal edges.
All pieces that are not variable pieces are contained within a single gadget.

(a): anchor, (b): swap, (c): adder, (d): teeter-totter, (e): seesaw, (f): gramophone.

Canonical placements.
Recall that we define canonical placements of each variable piece.
We do not define individual canonical placements of pieces that are not variable pieces, but instead we define canonical placements of all pieces of one or more gadgets:
A placement of a set of pieces is canonical if (1) the placement is valid (i.e., the pieces are in $\cont$ and are non-overlapping), (2) all variable pieces have a canonical placement, and (3) the pieces have certain releationships such as edge-edge contacts between each other.
Part (3) will be specified for each gadget individually.

Preservation of solutions.
The following lemma will be used to prove that for every solution to the formula $\Phi$, there is a canonical placement where the pieces encode that solution, meaning that for each variable $x$, all variable pieces representing $x$ encode the same value of $x$ as in the solution.
Define $\gadgets$ to be the total number of gadgets, and let $\p_i$ denote the set of all pieces introduced in the first $i$ gadgets, where $i\in\{0,\ldots,\gadgets\}$, so that $\p_0\mydef\emptyset$.
The proof will be given in the sections describing the individual types of gadgets.

Consider any $i\in\{1,\ldots,\gadgets\}$ and suppose that for every solution to $\Phi$, there is a canonical placement of the pieces $\p_{i-1}$ that encodes that solution.
Then the same holds for $\p_i$.

Soundness of the reduction.
As mentioned, each variable $x$ will be represented by many variable pieces in the complete construction.
A difficulty is that conceivably, such a piece may not be placed in a way that encodes a value of $x$.
Even if all the pieces happen to be placed such that they do encode values of $x$, these values could be different and therefore not represent a solution to the formula $\Phi$.

For a small number $\Delta\geq \delta$, we are going to introduce class of placements called aligned $\Delta$-placements.
These are defined from the canonical placements by relaxing the requirements a bit.
In an aligned $\Delta$-placements, each variable piece must be placed so that it encodes a value, but it may slide $\Delta$ sideways from the middle placement instead of at most $\delta$ as for the canonical placements.
The requirements to the other pieces are likewise relaxed and will be given later.
The values encoded by the variable pieces in an aligned $\Delta$-placement may therefore conceivably be outside the required range $[1/2,2]$.
The following lemma tells us that this is not the case for $\Delta$ sufficiently small.
In fact, the existence of such a placement is enough to ensure that $\I$ has a solution.
The number $\mu$ is the slack of the construction defined as the area of the container $\cont$ minus the total area of the pieces $\p$, and as will be explained later, $\mu=O(n^{-296})$ in our construction.
The number $g=O(n^4)$ is the number of gadgets.

In an aligned $g\slack$-placement, all pieces representing a variable $x$ encode the value of $x$ consistently (i.e., they all encode the same value of $x$) and the value is in the range $[1/2,2]$.
Furthermore, these values of the variables satisfy the addition and inversion constraints of $\Phi$.

In fact, it will follow from Lemma <ref> that every aligned $g\slack$-placement is canonical, but this is not important for our proof of Theorem <ref>.
The main work in proving the theorem will be to prove the following lemma.

Every valid placement is an aligned $g\slack$-placement.

The proof of Theorem <ref> is now straight-forward:

If $\I$ has a solution, it follows directly from repeated use of Lemma <ref> that there is a valid placement.
Suppose now that there is a valid placement.
By Lemma <ref>, the placement is an aligned $g\slack$-placement.
By Lemma <ref>, this placement encodes the variables consistently and in a way that respects the range $[1/2,2]$ and such that all addition and inversion constraints are satisfied.
Therefore, $\I$ has a solution.

In the following we will describe the tools needed to prove Lemma <ref>.

The slack of the construction.
The slack of an instance of a packing problem is the area of the container minus the total area of the pieces, and we denote it by $\slack$.
and define their canonical placements.
Our construction will be described as depending on the number $\delta\mydef n^{-300}$.
We need the slack to be very small in order to use the fingerprinting technique which will be described later.
In Section <ref>, we show that $\slack=O(g\delta)=O(n^{-296})$ in our construction.

We now give an upper bound on the slack of the complete construction.
We place each variable piece so that it encodes the middle value of the interval $I(x)$ of the variable $x$ it represents.
By checking each type of gadget, it is straightforward to verify that this can be realized as a canonical (and thus valid) placement of the pieces in all gadgets except for the adders, where there might be a small overlap of the pieces.
Therefore, the area of the empty space in this placement is at least $\slack$, so we bound $\slack$ from above by bounding this area from above.
The empty space in each gadget will appear as a thin layer along some of the edges of the pieces in the gadget.
This layer has thickness $O(\delta)$, and the edges along which it appears have total length $O(1)$, so the area is $O(\delta)$ in each gadget.
There will be no empty space outside the gadgets because that space will be completely covered by variable pieces.
Since the final construction has $g=O(N)=O(n^4)$ gadgets, it follows that the total slack is $\slack=O(n^4\delta)=O(n^{-296})$.
It may seem a little odd to measure the slack in this indirect way, but we found it to be the easiest way to get the bound since we do not explicitly specify the area of the container or the pieces in our construction.

In order to prove Lemma <ref>, we first show that every piece must be placed very close to a canonical placement using a technique we call fingerprinting.
To grasp the idea of this technique, we first present another simpler technique that only works for non-convex pieces, and which we call the jigsaw puzzle technique for obvious reasons, see Figure <ref> (a).
The idea behind this technique is to force each piece $p_1$
to be at a specific position by creating a pocket of the container and a corresponding
augmentation of the piece $p_1$ intended to be placed there.
This is done in a way that only the piece $p_1$ has an augmentation that fits into the pocket, just as the principle behind a jigsaw puzzle, and it can be done in a way that gives the piece freedom to slide back and forth by a slight amount or rotate, etc.
The pocket can also be created in another piece $p_2$ if $p_1$ is intended to be placed next to $p_2$.
Making enough of these pairs of pockets and extensions, we can therefore deduce where all the pieces are placed in all valid placements.

(a): A pocket and an augmentation that fit perfectly together as in a jigsaw puzzle.
(b): A wedge of the empty space and a piece which fit together.
(c): The corner of the piece we are fingerprinting is marked with a dot.
(d) and (e): Two examples where space is wasted because a wedge is not occupied by a piece with a matching angle.

Unfortunately, the jigsaw puzzle technique is not directly realizable with convex pieces.[In fact, the jigsaw puzzle technique can be used to prove $\ER$-hardness of packing problems with non-convex pieces in a much simpler way than the proofs of this paper, but since we anyway need to use the more involved fingerprinting technique for convex pieces, we stick to that in all cases.]
In fingerprinting, instead of a complicated augmentation, we only work with a piece $p_1$ with a convex corner $c$ of a specific angle $\alpha_1$.
In the canonical placements, the empty space left by the other pieces forms a wedge with apex corner $d$ of angle $\alpha_1$ which can thus be covered very efficiently by $p_1$ by placing the corner $c$ at or very close to $d$, as in Figure <ref> (b).
We make sure that every corner of every other piece has an angle $\alpha_2$ significantly different from $\alpha_1$, in the sense that $|\alpha_2-\alpha_1|=\Omega(N^{-2})$.
It should likewise hold that the total angle of any combination of corners of other pieces is different from $\alpha_1$ in that sense.
Furthermore, the slack $\slack$ is teeny tiny, as described above.
As a result, we can show that if $c$ is not placed very close to $d$, this will result in the empty space in a neighbourhood around $d$ with an area exceeding $\slack$, because no other piece (or combination of pieces) can cover that neighbourhood efficiently, illustrated in Figure <ref> (d-e).
In our constructions, fingerprinted corners are marked with a dot; see Figure <ref> (c).
For technical reasons, the fingerprinted corners must have angles in the range from $5\pi/180$ to $\pi/2$.

We add a few remarks about the use of fingerprinting.
First of all, the situation shown in Figure <ref> (b) is simplified.
In our applications, the fat segments (bounding the empty space left by the other pieces) do not need to meet at the apex corner $d$, since a short portion (of length $O(\delta)$) close to the corner can be missing.
Furthermore, the angle between the two fat segments does not have to be exactly $\alpha_1$ before the technique can be used; just very close to $\alpha_1$ (this will be important when we are fingerprinting more than one piece in a row).

Second, the fingerprinting does not imply that the piece $p_1$ must be placed with the corner $c$ coincident with $d$, but only that the distance $\|cd\|$ has to be small.
This is used deliberately in our constructions, since it allows for the piece $p_1$ to move slightly.

Third, when we introduce a new gadget and its $k$ new pieces $p_i,\ldots,p_{i+k-1}$,
we use fingerprinting iteratively to argue where the new pieces must be placed.
Here, the $j$'th piece $p_{i+j-1}$, $j\in\{1,\ldots,k\}$, can be fingerprinted in a wedge of the empty space formed by the preceding pieces $p_i,\ldots,p_{i+j-2}$.
However, the bound on the uncertainty of where $p_{i+j-1}$ is placed increases with $j$.
Slightly simplified, the bound grows as $O(n^{O(j)}\sqrt\slack)$, and we need the bound to be at most some small constant to be of any use.
We prefer to create an instance where we need only a logarithmic number of bits to represent the coordinates of the container and the pieces, since this will prove that the packing problems are strongly $\ER$-hard.
It is therefore important that we only apply fingerprinting iteratively a constant number of times, i.e., that $k=O(1)$, as we will otherwise need to choose the slack to smaller than $n^{-q}$ for every constant $q>0$, and then it will require a superlogarithmic number of bits to represent the coordinates of our instance.
In the construction, we will always have $k\leq 7$ and we can do with choosing $\delta\mydef n^{-300}$ so that $\slack=O(n^{-296})$.

After using fingerprinting iteratively a constant number of times for the new pieces, we use other techniques, such as the alignment (to be described in the sequel), to argue about their placement.
In Section <ref>, we will develop the fingerprinting technique in detail.
We consider this part the technically most challenging of the paper.
The technique is versatile and can likely be used in other reductions to packing.

As the conditions for the fingerprinting technique are technical, we will list them in Section <ref> in detail.
We will show for each gadget that those conditions are met.

Choosing unique angles.
As described in the previous paragraph, whenever we apply the fingerprinting technique to argue that a corner with angle $\alpha_1$ of some piece is placed close to some specific point in the container, we need that every combination of corners of the other pieces have angles that sum to an angle $\alpha_2$ such that $|\alpha_2-\alpha_1|=\Omega(N^{-2})$.
This will be called the unique angle property.
In order to obtain this property, the construction will be designed so that each piece has a special corner where the angle can be chosen freely (within some interval of angles of size $\Omega(1)$).
Likewise, the wedge (where the special corner is intended to be placed) formed by the boundary of the container or the other pieces is flexible, so that the angle of the wedge can match the chosen angle of the corner.
The fingerprinting technique will be applied to the special corner.
In our figures, fingerprinted corners are marked with a dot, as in Figure <ref> (c).
The following lemma is used to choose these free angles such that we get the unique angle property.

Let $S_k\mydef \{i/k+1/2k^2\mid i\in\{1,\ldots,k\}\}$, consider a subset $R\subseteq S$, and let $x\mydef \sum_{r\in R} r$.
If $x\in S_k$, then $R=\{x\}$.

If $R$ consists of $m$ elements, then $x$ has the form $j/k+m/2k^2$ for some $j\in\N$.
A number of this form, for $m\leq k$, can only be in $S_k$ if $m=1$.

The lemma provides a set of $k$ numbers in a range of size $O(1)$ and any number is $\Omega(k^{-2})$ away from the sum of any combination of other numbers.
We multiply the numbers in $S_k$ by $\pi$ to get a set of rational angles and choose the free angles from such a set $\pi S_k$, for $k=O(N)$.
We need to use $k>N$ since the free angles are restricted to various subintervals of $[0,\pi]$, so we choose $k$ so large that $\pi S_k$ contains enough angles for each of these subintervals.
However, as each subinterval has size $\Omega(1)$, we can do with $k=O(N)$.

Proof structure of Lemma <ref>.
In the proof of Lemma <ref>, we use the fingerprinting technique to prove that in every valid placement, the pieces are placed almost as in a canonical placement.
To explain the structure of the argument in more detail, we need some notions of placements that are close to being canonical, which will be defined in the following paragraph.

Almost-canonical placements and aligned placements.
We say that a valid placement of the pieces of a gadget is almost-canonical if there exists rigid motions that move the pieces to a canonical placement such that every point in each piece is moved a distance of at most $n^{-1}$ (in other words, the displacement between the actual placement and the canonical placement of each piece is $n^{-1}$).

We say that a placement of the pieces of a gadget is an aligned $\Delta$-placement for $\Delta\geq\delta$ if (i) the placement is almost-canonical, and (ii) for each variable $x$, each variable piece representing $x$ is rotated and has $y$-coordinates as in the canonical placements and encodes a value in the range $[m-\Delta,m+\Delta]$, where $m$ is the middle value of the interval $I(x)$.
Note that since the placement is almost-canonical, we can always assume $\Delta\leq n^{-1}+\delta=n^{-1}+n^{-300}$.

The following lemma says that the pieces of every new gadget can be assumed to be almost-canonical if the preceding pieces have an aligned $\Delta$-placement.
Recall that $\p_i$ is the set of all pieces introduced in the first $i$ gadgets, where $i\in\{0,\ldots,\gadgets\}$, so that $\p_0\mydef\emptyset$.
The lemma will follow from the use of fingerprinting, and the proof will be given in the sections describing the individual types of gadgets.

For any $i\in\{1,\ldots,\gadgets\}$, consider a valid placement $P$ (of all the pieces) for which the pieces $\p_{i-1}$
have an aligned $(i-1)\slack$-placement.
It then holds for $P$ that the pieces $\p_i$ have an almost-canonical placement.

Left: The alignment segment $\ell$ makes us conclude that the pieces must be horizontally aligned: otherwise, they would overlap, cross the container boundary, or cover more of the alignment segment than what is available.
Right: An abstract drawing of the dependency graphs of the instance we get from the wiring diagram in Figure <ref> and how the graphs connect to the gadgets for addition and inversion constraints.
The number of vertices on the cycles and paths are neither important nor correct.

*Aligning pieces.
Once we know that the pieces $\p_i$ have an almost-canonical placement, provided by the previous lemma, we can use so-called alignment segments to further restrict where the new pieces $\p_i\setminus\p_{i-1}$ introduced in gadget $i$ can be placed.
In particular, we will be able to fix the rotations of some pieces to be as in the canonical placements.
The idea is sketched in Figure <ref> (left).
From the rough placements we get from fingerprinting, we know that a set of the pieces each has a pair parallel edges that are both cut through by an alignment segment $\ell$.
If we sum the distance between the two parallel edges over all the pieces, we get exactly the length of $\ell$.
Since the portions of $\ell$ covered by the pieces must be pairwise disjoint in a valid placement, we can conclude that the pieces have to be rotated so that the parallel edges are perpendicular to $\ell$.
This technique will be used to prove the following lemma for each gadget individually.
Using the lemma repeatedly together with Lemma <ref>, we get that every valid placement is also an aligned $\gadgets\slack$-placement, proving Lemma <ref>.

For any $i\in\{1,\ldots,\gadgets\}$, consider a valid placement $P$ (of all the pieces) for which the pieces $\p_{i-1}$
have an aligned $(i-1)\slack$-placement and the pieces $\p_i$ have an almost-canonical placement.
It then holds for $P$ that the pieces $\p_i$ have an aligned $i\slack$-placement.

It now remains to prove Lemma <ref>.

Proof structure of Lemma <ref>.
The proof of Lemma <ref> goes along the following lines.
In an aligned $\gadgets\slack$-placement, each variable piece $p_x$ encodes a value for the variable $x$ it is representing, which we will denote by $\enc{p_x}$.
The problem is that different pieces representing the same variable $x$ may conceivably not encode the value consistently.
However, recall that we build lanes of pieces on top of the two wires $\overrightarrow x,\overleftarrow x$, and these meet at the left and right endpoints of the wires.
We prove that the values encoded by these pieces $p_1,\ldots,p_m$ make a cycle of inequalities: $\enc{p_1}\leq\enc{p_2}\leq\cdots\leq\enc{p_m}\leq\enc{p_1}$.
It thus follows that all these pieces encode a value of $x$ consistently.

Furthermore, the anchors, which are the gadgets that we place at the left and right endpoints of the wires $\overrightarrow x,\overleftarrow x$, will ensure that $\enc{p_1}\in[1/2,2]$, so that the encoded values are in the correct range.

In our construction, we also make additional lanes of pieces going to the addition and inversion gadgets.
The functionality of the specific gadgets and the inequalities we get between the encoded values of pieces in these lanes implies that the addition and inversion inequalities of $\Phi$ are all satisfied.
In order to describe the structure of the argument, we introduce a graph $G_x$ for each variable $x$ as described in the next paragraph.

Dependency graph of variable pieces.
For each variable $x$, we introduce a directed dependency graph $G_x$.
The vertices of $G_x$ are the variable pieces representing $x$.
Consider a gadget and two variable pieces $p_1,p_2$ appearing in the gadget and both representing $x$.
We add an edge from $p_1$ to $p_2$ in $G_x$ if $p_1$ is an entering right-oriented piece or an exiting left-oriented piece and $p_2$ is an exiting right-oriented piece or an entering left-oriented piece.
In crossings between the two wires $\overrightarrow x,\overleftarrow x$ representing $x$, there will be a swap where this rule introduces unintended edges, so we make one exception described in Section <ref> where the swap is described in detail.

The following lemma is going to follow trivially from the way we make the lanes on top of the wires $\overrightarrow x,\overleftarrow x$ for each variable $x$, and the way we connect the gadgets representing addition and inversion inequalities to these lanes.
See Figure <ref> (right) for an illustration.

For each variable $x$, the graph $G_x$ consists of a directed cycle $K_x$ with some directed paths attached to it (oriented towards or away from $K_x$).
The vertices of the cycle $K_x$ are the variable pieces appearing on the wire $\overrightarrow x$ from left to right and the wire $\overleftarrow x$ from right to left in this order.
For each path attached to $K_x$, the vertex farthest from $K_x$ is a piece entering a gadget representing an addition or inversion constraint.

In the following, we consider a given aligned $\gadgets\slack$-placement of all the pieces.
Since all edges of $G_x$ are between pieces appearing in the same gadget, the following lemma will be proven for each gadget individually.

Consider a variable $x$ and an edge $(p_1,p_2)$ of $G_x$.
Then $\enc{p_1}\leq \enc{p_2}$.

From Lemma <ref> and <ref>, we now get the following (except that the part about the anchor gadget will be proven in Section <ref>).

For each variable $x$, all the pieces of the cycle $K_x$ encode the value of $x$ consistently.
Furthermore, due to the design of the anchor gadget, the value is in $[1/2,2]$.

By the above lemma, we may write $\enc{K_x}$ to denote the value represented by all pieces of $K_x$.

Addition and inversion gadgets work.
We will show in Section <ref> and Section <ref> that the addition and inversion gadgets actually enforce addition
and inversion constraints as they are supposed to.
This entails showing that the gadgets implement the addition or inversion operations in a geometric sense and also that the variable pieces of the gadgets are correctly connected to the cycles in the respective dependency graphs.
In particular, we will show the following two lemmas.

For every addition constraint $x+y= z$ of $\Phi$, we have $\enc{K_x}+\enc{K_y}=\enc{K_z}$.

For every inversion constraint $x\cdot y= 1$ of $\Phi$, we have $\enc{K_x} \cdot \enc{K_y}=1$.

From the proofs of the lemmas, we get that not only the variable pieces of the cycles $K_x$ encode the value of $x$ consistently, but also the pieces of the directed paths that lead to the addition and inversion gadgets.
Together with the statement of Lemma <ref> that the values $\enc{K_x}$ are in $[1/2,2]$, we then have a proof of Lemma <ref>.

Square container.
In Section <ref>, we describe a reduction from problems of type   to □ and from to □.[There is in fact a much simpler reduction from to □, but it requires pieces of non-constant complexity:
We simply introduce a huge square piece and remove a hole from it with a shape as the original container of type .
We also remove a thin corridor from that hole to the boundary to make the piece simply-connected.
Then the hole in the piece will act as the container for the other pieces.]
It will be crucial that the container $\cont$ is $4$-monotone, as defined below.[In some cases, the gadgets that we describe might at first appear slightly more convoluted than necessary because we want $\cont$ to have this property.]

A simple closed curve $\gamma$ is 4-monotone if $\gamma$ can be partitioned into four parts $\gamma_1,\ldots,\gamma_4$ in counterclockwise order that move monotonically down, to the right, up, and to the left, respectively.
A (curved) polygon $\polQ$ is $4$-monotone if the boundary of $\polQ$ is a $4$-monotone curve.

In the reductions to each problem mentioned in Theorem <ref>, the resulting container is $4$-monotone.

The boundary of the resulting container has a left and a right staircase, $\gamma_1$ and $\gamma_3$, created by the left and right anchors, respectively, and these staircases are $y$-monotone, and their upper an lower endpoints are horizontally aligned.
The lower endpoints of the staircases $\gamma_1$ and $\gamma_3$ are connected by a single horizontal line segment $\gamma_2$ bounding the bottom lane from below.
The upper endpoints of the staircases are connected by a curve $\gamma_4$ which bound the topmost lane and the addition and inversion gadgets from above.
The curve $\gamma_4$ is $x$-monotone, as can easily be verified by inspecting the boundary added due to each type of constraint gadget.
Hence, the container is $4$-monotone.

Construction used in the reduction to packing problems with a square container.
The space left by the exterior pieces (blue, green, orange, and turquoise) is exactly the $4$-monotone container $\cont$ of the instance we are reducing from.

We get from the lemma that the packing problems are even $\ER$-hard for $4$-monotone containers.
Let $\I_1$ be an instance of a packing problem where the container $\cont\mydef\cont(\I_1)$ is 4-monotone.
We place $\cont$ in the middle of a larger square and fill out the area around $\cont$ with pieces in a careful way; the details are given in Section <ref> and Figure <ref> shows an example of the construction.
We call these new pieces the exterior pieces, whereas we call the pieces of $\I_1$ the inner pieces.
Using fingerprinting and other arguments, we are able to prove that if there exists a valid packing of the resulting instance, then there exists one where the exterior pieces are placed as they are intended to.
Then the space left for the inner pieces is exactly the container $\cont$.
Therefore, there exists a valid placement of the pieces in the resulting instance if and only if there is one of the inner pieces in $\cont$.
We get the results in the third row of Table <ref> as expressed by the following theorem.

The problems □are -hard, where

Our reductions imply so-called Mnëv-universality type results.
They show algebraic and topological equivalence of packing problems to compact semi-algebraic sets.

As we will argue about the entire solution space, we will show the following lemma, which will be proven for each gadget individually and in Section <ref>.
The proof builds upon Lemma <ref> and Lemma <ref>.

Every valid placement is canonical.

In Section <ref>, we will show the following two theorems.

Let $P$ be one of the packing problems
indicated as -complete in Table <ref>.
Let $\F_1,\F_2$ be algebraic field extensions of such that $\Q \subseteq \F_1\subsetneq \F_2 \subset \R$. Then there exists
an instance $(\p,C)$ of $P$
that has a solution in $\F_2$, but
none in $\F_1$.

Let $T$ be a compact semi-algebraic set, and
let $P$ be one of the packing problems
indicated as -complete in Table <ref>.
Then there is an instance $(\p,C)$ of $P$ such that $T$ is homotopy equivalent to the
solution space $V(\p,C)$.

§ COMPLETE EXAMPLE

A sketch of the instance of , broken over six lines, we get from the wiring diagram in Figure <ref> (except that the order of the inversion gadgets has been swapped to decrease the number of crossings).
The addition and inversion gadgets are marked with gray boxes.

§ PRELIMINARIES

This section contains three parts with definitions and conventions used in the rest of the paper.
The first part concerns the way we encode geometric objects and motions.
The second part defines some general geometric definitions, which we will use heavily in Section <ref> about fingerprinting.
The third part is concerned with different notions of equivalence of solution spaces and become relevant in Section <ref> about and Section <ref> about universality.
In the end of the section, we prove the folklore lemma that  is in .

§.§ Encoding Polygons and Motions

Orientation of polygons.
We always consider a simple polygon (or a curved polygon) to be oriented in counterclockwise direction, which makes it well-defined to talk about the edge preceding or succeeding a given corner, etc.

*Representation of curved segments.
Recall that the convex (  ) or curved polygons (  ) pieces or containers that we use have boundaries which are a finite union of line segments and curves contained in hyperbolae.
We assume that these curved parts will be given implicitly, by a polynomial equation and two endpoints, see Figure <ref>.

The shape can be encoded by
$v_0 = (2,0.5), v_1 = (2,2)$, $v_2 = (0.5,2)$, $x \cdot y =1$, $v_0$.

Motion and Placement.
We encode a rotation by a rotation matrix, which is a matrix $M$ of
the form

\[M = \begin{pmatrix}
a & -b \\
b & a
\end{pmatrix},\]

with $\det M = 1$.
From a translation $t\in\R^2$ and a rotation $M$, we get a motion $m \mydef (t,M)$.
If only translations are allowed, we require that $M$ is the identity.

When we define the solution space $V(\I)$, then we also allow rotations $M$ such that $\det M>0$.
Note that we can normalize a matrix by simply
multiplying every entry with $\sqrt{\det M}$.
The reason we do not require the rotation to be normalized is related to the algebraic universality, which we will show in Section <ref>.
The introduction of square-roots would destroy this algebraic-universality.

Given a piece $p$ and a motion
$m = (M,t)$,
then we denote by $p^m$ the piece $p$ after moving $p$
according to $m$, i.e.,

\[\pl p m \mydef \{Mx + t : x\in p\}.\]

The set $\pl p m$ is the placement of $p$ by $m$.
Given a tuple of $\mathbf{p} = (p_1,\ldots,p_k)$ of pieces
and a tuple $\m = (m_1,\ldots,m_k)$ of motions,
then we denote by

\[\p^\m = (p_1^{m_1},\ldots, p_k^{m_k})\]
the placement
of $\p$ by $\m$.
We may write $\pl {p_i}\m$ instead of $\pl {p_i}{m_i}$.

Given a container $\cont$ and pieces $\p=(p_1,\ldots,p_k)$ and a motion $\m$,
we say $\m$ and $\p^\m$ are a valid motion and placement, respectively, if $\pl {p_i}\m\subset C$ for all $i$ and $\pl {p_i}\m$ and $\pl {p_j}\m$ are interior-disjoint for all $i\neq j$.

§.§ Elementary Geometry

Let $ab$ and $cd$ be two (oriented) line segments.
The angle between $ab$ and $cd$ is the minimum angle the $ab$ can be turned such that $ab$ and $cd$ become parallel and point in the same direction, i.e., $(b-a)\cdot (d-c)>0$.

Consider two motions $m_1$ and $m_2$ of a piece $p$.
The displacement between $m_1$ and $m_2$ is
\sup_{x\in p}\|\pl x{m_1}-\pl x{m_2}\|.
The displacement angle is the absolute difference in how much $m_1$ and $m_2$ rotate $p$ in the interval $[0,\pi]$.

Given a compact
set $S$ in the plane, we denote by
$\area(S)$ the area of $S$.
All sets that we consider will be compact.

Given a container $\cont$ and pieces ,
we define the slack as
$\slack(\cont,\p) = \area(\cont) - \sum_{p\in\p}\area(p)$.

Given a compact set $S$ in the plane, the diameter of $S$ is defined as $\diam(S)\mydef \max_{a,b\in S}\|ab\|$.

Let $A\subset\R^2$. Then $A^c=\{x\in\R^2\mid x\notin A\}$.
Let $A,B\subset\R^2$.
Then we denote the Minkowski sum as $A\oplus B\mydef \{a+b\mid a\in A,b\in B\}$ and the Minkowski difference as $A\ominus B\mydef (A^c\oplus B)^c$.

§.§ Universality

A universality statement says that for every
object of type A, there exists an object of type B
such that A and B are equivalent in some sense C.
In Theorem <ref>, to be stated and proved in the next section, we have compact
solution spaces of formulae (i.e., compact semi-algebraic sets) as objects of type A,
solution spaces of formulas are objects of type B,
and we preserve algorithmic, topological and
algebraic properties.
Specifically, we show rational equivalence between the solution spaces and that those of formulae are linear extensions of those of formulae.
In Section <ref>, we will show some
weaker forms of equivalence for all our packing problems.

Given a packing instance $\I = (C,\p)$,
we define
$V(\I) \mydef \{\m \in \R^{6n} : \m \text{ is a valid motion}\}$
to be the solution space of $\I$.

For the definition of solution space we explicitly also allow non-normalized rotation matrices $M$, which are matrices of the form $M=\lambda M'$ for a scalar $\lambda>0$ and a rotation matrix $M'$.
To see how this can be useful consider the
rotation matrix $M'$ of a $45^\circ$ rotation, which has irrational entries:
\[M' \mydef
\begin{pmatrix}
\cos 45^\circ & -\sin 45^\circ \\
\sin 45^\circ & \cos 45^\circ   \\
\end{pmatrix}
\begin{pmatrix}
\frac{1}{\sqrt{2}} & -\frac{1}{\sqrt{2}} \\
\frac{1}{\sqrt{2}} & \frac{1}{\sqrt{2}}.   \\
\end{pmatrix}.
\]

We can also easily express this rotation
by the rational matrix

\[M \mydef
\begin{pmatrix}
1 & -1 \\
1 & 1.  \\
\end{pmatrix}
\]

Note that if we want to rotate a vector $v$, we have to normalize the matrix first,
which is possible if we allow taking square-roots in our model of computation.

Given a polynomial $p\in \Z[x_1,\ldots,x_n]$, we define $V(p) \mydef V(p=0) = \{\mathbb t\in \R^n : p(\mathbb t) = 0\}$
to be the variety or the solution space of $p$.

Consider two sets $V\subseteq \R^n$ and $W\subseteq \R^m$ and a function $f:V\rightarrow W$.
We say that $f$ is a homeomorphism if $f$ is
bijective, continuous, and the inverse $f^{-1}$ is
continuous as well.

Write $f$ as its components $(f_1,\ldots,f_m)$, where $f_i:V\longrightarrow\R$ for each $i\in\{1,\ldots,m\}$.
Then $f$ is rational if each function $f_i$ is the ratio of two polynomials.

The sets $V$ and $W$ are rationally equivalent
if there exists a homeomorphism
$f : V \longrightarrow W$
such that both $f$ and $f^{-1}$ are rational functions.
In that case, we write $V\simeq W$.

Be aware that the term , that we define below, has other meanings in other contexts.

Given two sets $V\subseteq \R^n$ and $W\subseteq \R^m$, we say that $W$ is a
of $V$ if
there is an orthogonal projection $\pi:\R^m\longrightarrow \R^n$
and two vectors $\mathbf a,\mathbf b\in \Q^{n}$
such that the mapping $l: W\longrightarrow V$ defined by

\[l(x) \mydef \mathbf a \odot \pi (\mathbf x) + \mathbf b\]

is a continuous bijection.
Here, $\mathbf c \odot \mathbf y $
denotes the elementwise product $(c_1d_1,\ldots,c_nd_n)\in\R^n$ for $\mathbf c=(c_1,\ldots,c_n)$ and $\mathbf d=(d_1,\ldots,d_n)$.
We denote that $W$ is a linear extension of $V$ as $V\leqlin W$.

Rational equivalence and linear extension are both transitive relations, i.e., if $U\simeq V$ and $V\simeq W$, then $U\simeq W$, and
if $U\leqlin V$ and $V\leqlin W$, then $U\leqlin W$.

Furthermore, for a compact set $V$, if $V\simeq W$ or $V\leqlin W$, then $W$ is compact as well.

$V \mydef [1,2]$ and $W \mydef  \{(x,y): x\in [1,2],\  x = y^2 \}$.
Then $W$ is not a linear extension of $V$, and  $V$ and $W$
are not rationally equivalent, as $W$ has two connected components.

A continuous deformation from left to right.
The two shapes are not homeomorphic, but homotopy equivalent.

Unfortunately, in the geometric reduction from to , our geometric reductions give neither rational equivalence, nor a linear extension.
The reason is that some pieces have room to move in the valid placements of the constructed instances.
Such pieces are sometimes called rattlers in the literature on packing problems.
We are still preserving some topological properties and also some algebraic properties.
To state these, we define homotopy equivalence.
Informally, two spaces are homotopy equivalent if one can be continuously deformed into the other; see Figure <ref> for an illustration.

We say two functions $f,g : X \rightarrow Y$ are homotopic if there exists a continuous map $G : [0,1]\times X \rightarrow Y$ such that $G(0,x) = f(x)$ and $G(1,x) = g(x)$, for all $x\in X$.

We say two topological spaces $S$, $T$  are homotopy equivalent if there are continuous maps $f:S\rightarrow T $ and
$g:T\rightarrow S$ such that $f \circ g $ is homotopic to $\id_{T}$ and $g \circ f $ is homotopic to $\id_{S}$.

Note that if $U\simeq V$ or $U\leqlin V$, then $U$ and $V$ are homotopy equivalent.

§.§ NP-Membership.

We now give a sketch of a proof of the following folklore lemma mentioned in the Introduction.

The problem is in NP.

We show that a valid placement can be specified as the translations of the pieces represented by a number of bits polynomial in the input size.
Consider a valid placement of the pieces.
For each pair of a segment $s$ and a corner $c$ (each of a piece or the container), we consider the line $\ell(s)$ containing $s$ and note which of the closed half-planes bounded by $\ell(s)$ contains $c$.
Then we build a linear program (LP) using that information in the natural way.
Here, the translation of each piece is described by two variables and for each pair $(s,c)$, we have one constraint involving at most four variables, enforcing $c$ to be on the correct side of $\ell(s)$.
It is easy to verify that the constraint is linear.
The solution of the LP gives a valid placement of every piece and as the LP is polynomial in the input, so is the number of the bits of the solution to the LP.
Note that if rotations are included, the corresponding constraints become non-linear.

§ AND

First recall the definition of formulae and the problem , repeated below.

The goal of this section is to prove the following extension of Theorem <ref>.

is -complete, even when $\delta=O(n^{-c})$ for any constant $c>0$.
Furthermore, for every instance $\Phi$ of where $V(\Phi)$ is compact,
there is an instance $\I$ of with formula $\Psi$ such that
$V(\Phi)$ and $V(\Psi)$ are rationally equivalent and $V(\Psi)$ is a of $V(\Phi)$.

We give a self-contained proof of the theorem except that we will need a few results from real algebraic geometry.
The reductions in Sections <ref>–<ref> rely on well-known techniques and can be considered folklore, but we need to phrase them differently than done earlier to obtain the latter part of Theorem <ref>.
The reductions in Sections <ref>–<ref> are new.

Naming the variables.

We typically denote a new variable with a multi-character symbol such as $\const{v}$.
Here, $v$ is an expression involving already known quantities, and $\const{v}$ should be thought of as a placeholder with that value.
In the case that $v$ is a constant, e.g., $v=2$ such that the variable is $\const{2}$, then we say that $\const{v}$ is a constant variable.
By constructing a constant variable $\const{v}$ in an formula $\Phi$, we mean introducing variables and constraints to $\Phi$ such that it follows that in every solution to $\Phi$, we have $\const{v}=v$.

The expression $v$ of a variable $\const{v}$ can also involve other parameters such as for instance $\const{x^2+2x+1}$.
In that case $\const{x^2+2x+1}$ should be thought of as a variable holding the value $x^2+2x+1$, where $x$ is another variable or a parameter of the problem.
It should follow from the assumptions or constraints introduced in the concrete case that $\const{x^2+2x+1}$ indeed has the value $x^2+2x+1$ in any solution to $\Phi$.

§.§ Reduction to Conjunctive Form

An formula $\Phi\mydef\Phi(x_1,\ldots,x_n)$ is a conjunction $C_1\land\ldots\land C_m$,
where $m\in \N$ and each $C_i$ is of one of the two forms

\begin{align*}
x\geq 0,\quad p(y_1,\ldots,y_l) = 0
\end{align*}

for $x,y_1,\ldots,y_l \in \{x_1, \ldots, x_n\}$ and $p$ is a polynomial.

Note that since there are no strict inequalities in a formula $\Phi$ in , the set $V(\Phi)$ is closed.

We show how to reduce a general formula
to an formula.
The reduction preserves rational equivalence and runs in linear time.
A similar reduction has been described by Schaefer and Štefankovič <cit.>.

Given an formula $\Phi$, we can in $O(|\Phi|)$ time compute an formula $\Psi$ such that $V(\Phi) \simeq V(\Psi)$ and $V(\Phi) \leqlin V(\Psi)$.

We start with an formula $\Phi$
and modify it repeatedly to attain an formula
Each modification leads
to an equivalent formula.
Our modifications can be summarized in four steps.
(1) Delete “$\lnot$”.
(2) Delete “$>$”.
(3) Move “$\geq$” to variables only.
(4) Delete “$\lor$”.
In the rest of this proof $p$ and $q$ denote polynomials.

Step (1): Here, we merely ”pull“ every negation $\lnot$
in front of every atomic predicate.
For instance
$\lnot(A\lor B\lor C)$ becomes
$(\lnot A\land \lnot  B\land \lnot C)$.
To see that this can be done in linear time,
note that the length of $\Phi$ is at least
the number of atomic predicates.
In the end of this process, every atomic predicate
is preceded by either a negation or not.
It may be that $\land$ and $\lor$ symbols are swapped,
but we count both as one symbol.

Thereafter each
atomic predicate preceded by $\lnot$ is replaced as follows:

\begin{align*}
\lnot (q > 0) \quad &\mapsto \quad -q \geq 0\\
\lnot (q = 0) \quad &\mapsto \quad (q > 0) \,  \lor \,  (-q > 0) \\
\lnot (q \geq 0)\quad  &\mapsto \quad -q > 0
\end{align*}

Those replacements are done repeatedly until there
are no occurrence of “$\lnot$” left in the formula.

Step (2): We replace each
inequality as follows:

\[q > 0 \quad \mapsto  \quad (q\cdot z-1 = 0) \ldots \land z\geq 0.\]

The dots indicate that the predicate $z\geq 0$ does not
immediately follow after $(q\cdot z-1 = 0)$, but will be
adjoined at the end of the new formula.
Furthermore, $z$ denotes a new variable.
Those replacements are done repeatedly until there
are no occurrence of “$>$” left in the formula.

Step (3): We replace all atomic predicates
of the form
$q \geq 0$
by the predicate
$q - z = 0$ and adjoin a new predicate
$z\geq 0$ at the the end of the formula.
Again $z$ denotes a new variable.

Step (4): We delete disjunctions as follows.
It will also be necessary to replace some conjunctions.
Let $\Phi$ be the formula
after Step (1)–(3).
Suppose that there is a disjunction somewhere in $\Phi$, and write it as $\Phi_1\lor\Phi_2$ for two sub-formulas $\Phi_1$ and $\Phi_2$.
Note that $\Phi_1\lor\Phi_2$ might just be a small part of $\Phi$ – there will in general be more of $\Phi$ to the right and left of this part.

We want to reduce each of $\Phi_i$ to a single polynomial equation, as follows.
Note that since we have already performed Step (1)–(3), there are no inequalities in $\Phi_i$.
Suppose that $\Phi_i$ is not already a single polynomial equation.
Then there must somewhere in $\Phi_i$ be either (i) a disjunction $p=0\lor q=0$ or (ii) a conjunction $p =0 \land q = 0$.
We now explain how to reduce each of these cases to a simpler case.

* Case (i):
We make the replacement

\[ p =0 \lor q = 0 \quad   \mapsto \quad p\cdot q=0.\]

* Case (ii):
We make the replacement

\[ p =0 \land q = 0 \quad  \mapsto \quad
x\cdot x +  y\cdot y = 0 \ldots
\land p -x = 0 \, \land\,  q -y = 0  .\]

Here, $x$ and $y$ are new variables.
As in Step (2), the part following the dots is appended at the end of the complete formula $\Phi$.

Eventually, we have reduced each $\Phi_i$ to a single polynomial equation.
Thus the original disjunction $\Phi_1\lor \Phi_2$ has the form as in Case (i), and we apply the replacement rule described there.

At first, it might seem easier in Case (ii)
to replace
$p =0 \land q = 0$ by $p\cdot p+q\cdot q = 0$.
However, we want our reduction to be linear and
the simplified step could, if done repeatedly,
lead to very long formulas.

With the replacement rules we have suggested, each iteration reduces the number of
disjunctions and conjunctions by one and increases the length of the formula by at most a constant.
Those replacements are done repeatedly until there
are no disjunctions left in the formula.

This reduction takes linear time and the
final formula $\Psi$ is in conjunctive form.
We need to describe a rational function

\[f : V(\Phi) \rightarrow V(\Psi).\]

Note that $\Psi$ has all the original variables $x_1,\ldots,x_n$
of $\Phi$ plus some additional variables,
which we denote by $z_1,\ldots,z_k$.
If $z\in \{z_1,\ldots,z_k\}$ is introduced
in step (2), it is assigned the value
$z = \frac{1}{q}$ and if it is introduced in
step (3) or (4), it is assigned the value $z = q$ for some polynomial $q$.
This defines $f$. Assume that $\Psi$ has
the free variables $x_1,\ldots,x_n,z_1,\ldots,z_k$,
where $z_1,\ldots,z_k$ are the variables introduced by the reduction.
\[f^{-1} : (x_1,\ldots,x_n,z_1,\ldots,z_k) \ \mapsto \ (x_1,\ldots,x_n).\]

Thus $f$ and $f^{-1}$ are
rational bijective functions.
Thus $f$ is a homeomorphism.
The description of $f^{-1}$ implies that
$V(\Psi)$ is a linear extension of $V(\Phi)$.

Note that the standard way to remove strict inequalities
\[q>0 \mapsto q\cdot y\cdot y -1 = 0.\]

However, this implies that $y = \pm \sqrt{1/q}$.
This transformation has two issues.
First, the number of solutions in a sense doubles, as the sign of $y$ is not fixed.
Second, irrational solutions are introduced
where before may have been only rational solutions.

§.§ Reduction to Compact Semi-Algebraic Sets

In the problem , we are given an formula $\Phi$ with the promise that $V(\Phi)$ is compact.
The goal is to decide if $V(\Phi)$ is non-empty.

In this section, we describe a reduction from
to .
We need a tool from
real algebraic geometry.
The following corollary has been pointed out
by Schaefer and Štefankovič <cit.> in a simplified form.

Let $\Phi$ be an instance of of complexity $L\geq 4$ such that $V(\Phi)$ is a non-empty subset of $\R^n$.
Let $B$ be the set of points in $\R^n$ at distance at most $2^{L^{8n}} = 2^{2^{8n\log L}}$ from the origin.
Then $B\cap V(\Phi)\neq\emptyset$.

Given an formula $\Phi\mydef\Phi(x_1,\ldots,x_n)$, we can in $O(|\Phi|+n\log|\Phi|)$ time create an formula $\Psi$ such that $V(\Psi)$ is compact and $V(\Phi) \neq\emptyset\Leftrightarrow V(\Psi)\neq\emptyset$.
In other words, there is a reduction from to in near-linear time.

Let an instance $\Phi$ of be given and define $k \mydef \lceil 8n\log L\rceil$.
To make an equivalent formula $\Psi$ such that $V(\Psi)$ is compact, we start by including all the variables and constraints of $\Phi$ in $\Psi$.
We then construct a large constant variable $\const{2^{2^k}}$ using exponentiation by squaring.

\begin{align*}
\const{2^{2^0}} -1-1 &= 0 \\
\const{2^{2^1}} - \const{2^{2^0}}\cdot \const{2^{2^0}} &= 0 \\
\vdots & \\
\const{2^{2^k}} - \const{2^{2^{k-1}}}\cdot \const{2^{2^{k-1}}} &= 0
\end{align*}

For each variable $x$ of $\Phi$, we now introduce the variables $\const{x-2^{2^k}}$ and $\const{x-2^{2^k}-x}$ and the constraints

\begin{align*}
\const{x+2^{2^k}}-x-\const{2^{2^k}} & =0 \\
\const{x+2^{2^k}} & \geq 0 \\
\const{2^{2^k}-x}-\const{2^{2^k}}+x & =0 \\
\const{2^{2^k}-x} & \geq 0.
\end{align*}

Note that this corresponds to introducing the constraint $-2^{2^k}\leq x\leq 2^{2^k}$ in $\Psi$.

It now follows by Corollary <ref> that

$$V(\Phi)\neq\emptyset\Leftrightarrow V(\Psi)\neq\emptyset.$$

Note that $V(\Psi)$ is compact since $\Psi$ contains no strict inequalities and each variable is bounded.
This finishes the proof.

Unfortunately, we do not have $V(\Phi)\simeq V(\Psi)$ in the above reduction.
That is not possible as it would imply, together with Lemma <ref>, that an open subset of $\R^n$ is homeomorphic to a compact set.
We can also not hope for the reduction to yield a linear extension, as a bounded set cannot be a linear extension of an unbounded one.

§.§ Reduction to

is an abbreviation for
Exitential Theory of the Reals with
Addition, Multiplication, and Inequalities.

An $\etrami$ formula $\Phi\mydef\Phi(x_1,\ldots,x_n)$ is a conjunction $C_1\land\ldots\land C_m$, where $m\geq 0$ and each $C_i$ is a constraint of one of the forms

x+y=z,\quad x\cdot y=z, \quad x\geq 0, \quad x=1

for $x,y,z \in \{x_1, \ldots, x_n\}$.

Given an instance of defined by a formula $\Phi$, we can in $O(|\Phi|)$ time construct
an formula $\Psi$ such that
$V(\Phi) \simeq V(\Psi)$
$V(\Phi) \leqlin V(\Psi)$.

Recall that $\Phi$ is a conjunction of atomic formulas of the form $p=0$ for a polynomial $p$ and $x\geq 0$ for a variable $x$.
Each polynomial $p$ may contain minuses, zeros, and ones.
The reduction has four steps.
In each step, we make changes to $\Phi$.
In the end, $\Phi$ has become a formula $\Psi$ with the desired properties.
In step (1)–(3), we remove unwanted ones, zeros and minuses by replacing them by constants.
In step (4), we eliminate complicated polynomials.

Step (1):
We introduce the constant variable $\const{1}$ and the constraint $\const{1}=1$ to $\Phi$.
We then replace all appearances of $1$ with $\const{1}$ in the atomic formulas of the form $p=0$.

Step (2):
We introduce the constant variable $\const{0}$ and the constraint $\const{1}+\const{0}=\const{1}$ to $\Phi$.
We then replace all appearances of $0$ with $\const{0}$ except in the constraints of the form $x\geq 0$.

Step (3):
We introduce the constant variable $\const{-1}$ and the constraint $\const{1}+\const{-1}=\const{0}$ to $\Phi$.
We then replace all appearances of minus with a multiplication by $\const{-1}$ in $\Phi$.
To be precise, we replace $-p$ with $+\const{-1}\cdot p$.

Step (4):
We replace bottom up every occurrence
of multiplication and addition by a new variable
and an extra addition or multiplication constraint,
which will be adjoined at the end of the formula.
Here are two examples of such replacements:

\begin{align*}
x_1 + x_2\cdot x_4 +x_5+x_6 = \const{0} \quad & \mapsto\quad x_1 + z_1 +x_5+x_6 = \const{0}\ldots\land z_1=x_2\cdot x_4 \\
x_1 + z_1 +x_5+x_6 = \const{0} \quad & \mapsto\quad z_2 +x_5+x_6 = \const{0}\ldots\land z_2=x_1+ z_1
\end{align*}

In this way every atomic predicate is eventually transformed to atomic predicates of or is of the form $x=\const{0}$.
In the latter case, we replace $x=\const{0}$ by $x+\const{0}=\const{0}$.

To see that the reduction is linear, note that
every replacement adds a constant to
the length of the formula.
Furthermore, at most linearly many
replacements will be done.

Let us show that this reduction preserves
rational equivalence and .
This is trivial for steps (1)–(3), as these just introduce constants in order to rewrite polynomials without using zeros, ones, and minuses.
In Step (4), we repeatedly make one of two types of steps, replacing either a multiplication or an addition.
Thus it is sufficient to show that one such step preserves all of those properties.
Consider a step where we go from $\Phi_1$ to
$\Phi_2$ and $\Phi_1$ has the variables
$x_1,\ldots,x_n$ and $\Phi_2$ has the variables
$x_1,\ldots,x_n,z$, with $z = x_i \diamond x_j$.
Here $\diamond$ is either multiplication or addition.
This defines $f$ as

\[(x_1,\ldots,x_n) \quad \mapsto \quad (x_1,\ldots,x_n, x_i \odot x_j),\]

and $f^{-1}$ is defined by

\[(x_1,\ldots,x_n,z) \quad \mapsto \quad (x_1,\ldots,x_n).\]

Both functions are rational and bijective, and $f^{-1}$ is an orthogonal projection.
This implies both rational equivalence and between $V(\Phi)$ and $V(\Psi)$.

§.§ Reduction to

For a number $\delta>0$, an -$\delta$ formula $\Phi\mydef \Phi(x_1,\ldots,x_n)$ is a conjunction $C_1\land\ldots\land C_m$, where $m\geq 0$ and each $C_i$ is a constraint of one of the forms

\[
x+y=z,\quad x\cdot y=z, \quad x\geq 0,\quad x=\delta
\]

for $x,y,z \in \{x_1, \ldots, x_n\}$.

An instance $\mathcal I\mydef [\Phi,\delta]$ of the problem is a number $\delta\mydef 2^{-l}$ for a positive integer $l$ and an -$\delta$ formula $\Phi$.
We are promised that $V(\Phi) \subset [-\delta,\delta]^n$.
The goal is to decide whether $V(\Phi) \neq \emptyset$.

We are going to present a reduction from the problem to .
As a preparation, we present another tool from
real algebraic geometry.
Schaefer <cit.> made the following simplification of a result from <cit.>, which we will use.
More refined statements can be found in <cit.>.

If a bounded semi-algebraic set in $\R^n$ has complexity at most
$L \geq 5n$, then all its points have distance at most $2^{2^{L+5}}$
from the origin.

Given an formula $\Phi$ such that $V(\Phi)$ is compact and a number $\delta\mydef 2^{-l}$, we can in $O(|\Phi|+l)$ time construct an instance $\mathcal I\mydef [\Psi,\delta]$ of such that
$V(\Phi) \simeq V(\Psi)$ and
$V(\Phi) \leqlin V(\Psi)$.

Let $\Phi$ be an instance of $\etrami$ with $n$ variables $x_1,\ldots,x_n$.
We construct an instance $\Psi$ of $\etrsmall$.

We set $\eps \mydef \delta\cdot 2^{-2^{L+5}}$, where $L\mydef|\Phi|$.
In $\Psi$, we first define a constant variable $\const{\eps}$.
This is obtained by exponentiation by squaring, using $O(L)$
new constant variables and constraints.
We first define $\const{\delta}$, $\const{0}$, and $\const{\delta\cdot 2^{-2^0}}$ by the equations

\begin{align*}
\const{\delta} & =\delta \\
\const{0}+\const{\delta} & = \const{\delta} \\
\const{\delta\cdot 2^{-2^0}}+\const{\delta\cdot 2^{-2^0}} & =\const{\delta}.
\end{align*}

We then use the following equations for all $i\in\{0,\ldots,L+4\}$,

\begin{align*}
\const{\delta\cdot 2^{-2^i}}\cdot\const{\delta\cdot 2^{-2^i}} & =\const{\delta^2\cdot 2^{-2^{i+1}}} \\
\const{\delta\cdot 2^{-2^{i+1}}}\cdot \const{\delta} & = \const{\delta^2\cdot 2^{-2^{i+1}}}.
\end{align*}

Finally, we define $\const{\eps}$ by the constraint $\const{\eps}+\const{0}=\const{\delta\cdot 2^{-2^{L+5}}}$.

In $\Psi$, we use the variables $\const{\eps x_1},\ldots,\const{\eps x_n}$ instead of
An equation of $\Phi$ of the form $x=1$ is transformed to the equation
$\const{\eps x} + \const{0}=\const{\eps}$ in $\Psi$.
An equation of $\Phi$ of the form $x+y=z$ is transformed to the equation
$\const{\eps x} + \const{\eps y} = \const{\eps z}$ of $\Psi$.
For an equation of $\Phi$ of the form $x\cdot y=z$, we also introduce a variable $\const{\eps^2 z}$ of $\Psi$ and the equations

\begin{align*}
\const{\eps x} \cdot \const{\eps y} & = \const{\eps^2 z} \\
\const{\eps}\cdot \const{\eps z} & = \const{\eps^2 z}.
\end{align*}

At last, constraints of the form
$x \geq 0$ become $\const{\eps x} \geq 0$.

We now describe a function $f : V(\Phi) \rightarrow V(\Psi)$ in order to show that $\Psi$ has the properties stated in the lemma.
Let $\mathbf x\mydef (x_1,\ldots,x_n)\in V(\Phi)$.
In order to define $f$, it suffices to specify the values of the variables of $\Psi$ depending on $\mathbf x$.
For all the constant variables $\const{c}$, we define $\const{c}\mydef c$.
Note that these are all rational constants.
For all $i\in\{1,\ldots,n\}$, we now define $\const{\eps x_i} \mydef \eps x_i$ and (when $\const{\eps^2 x_i}$ appears in $\Psi$) $\const{\eps^2 x_i} = \eps^2 x_i$.
Since $\mathbf x$ is a solution to $\Phi$, it follows from the constraints of $\Psi$ that these assignments are a solution to $\Psi$.

We need to verify that $\Psi$ defines an problem, i.e., that $\Psi$ satisfies the promise that $V(\Psi)\subset [-\delta,\delta]^m$, where $m$ is the number of variables of $\Psi$.
To this end, consider an assignment of the variables of $\Psi$ that satisfies all the constraints.
Note first that the constant variables are non-negative and at most $\delta$.
For the other variables, we consider the inverse $f^{-1}$, which is given by the assignment $x_i\mydef \const{\eps x_i}/\eps$ for all $i\in\{1,\ldots,n\}$.
It follows that this yields a solution to $\Phi$.
Since $V(\Phi)$ is compact, it follows from Corollary <ref> that $|\const{\eps x_i}/\eps|\leq 2^{2^{L+5}}$.
Hence $|\const{\eps x_i}|\leq \eps\cdot 2^{2^{L+5}}=\delta\cdot 2^{-2^{L+5}}\cdot 2^{2^{L+5}}=\delta$.
Similarly, when $\const{\eps^2 x_i}$ is a variable of $\Psi$, we get $|\const{\eps^2 x_i}|\leq \eps\cdot\delta<\delta$.

By the definitions of $f$ and $f^{-1}$, we have now established that $V(\Phi)\simeq V(\Psi)$ and $V(\Phi)\leqlin V(\Psi)$.
The length of $\Psi$ is $O(L)$ longer than the length of $\Phi$, and $\Psi$ can thus be computed in $O(|\Phi|)$ time.

is -complete, even when $\delta=O(n^{-c})$ for any constant $c>0$, where $n$ is the number of variables in the -$\delta$ formula.

Let an formula $\Phi$ with $n$ variables be given.
Let $l\in\N$ be such that $2^{-l}\leq n^{-c}$ and define $\delta\mydef 2^{-l}$.
The reduction of Lemma <ref> gives an equivalent instance $\mathcal I\mydef[\Psi,\delta]$ of in time $O(|\Phi|+l)$.
Since $l=O(\log n)$, the reduction takes polynomial time.

§.§ Reduction to

An formula $\Phi\mydef \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

\begin{align*}
x+y=z,\quad x\cdot y=z
\end{align*}

for $x,y,z \in \{x_1, \ldots, x_n\}$.

An instance $\mathcal I\mydef \left[\Phi,\delta,(I(x_1),\ldots,I(x_n))\right]$ of the problem is an formula $\Phi$, a number $\delta\mydef 2^{-l}$ for a positive integer $l$, and, for each variable $x\in\{x_1,\ldots,x_n\}$, an interval $I(x)\subseteq [1/2,2]$  such that $|I(x)|\leq 2 \delta$.
For each multiplication constraint $x\cdot y=z$, we have $I(x)\subset [1-\delta,1+\delta]$ and $I(y)\subset [1-\delta,1+\delta]$.

We are promised that $V(\Phi)\subset I(x_1)\times\cdots\times I(x_n)$.
The goal is to decide whether $V(\Phi)\neq\emptyset$.

We will now present a reduction from the problem to .
The following technical lemma is a handy tool to show that all variables $x$ of the constructed problem are in the ranges $I(x)$ we are going to specify.

Let $g(x,y) \mydef  \frac{p(x,y)}{q(x,y)}$ be a rational function such that

\begin{align*}
p(x,y) & \mydef a_1 \ x^2 + a_2 \ xy + a_3 \ y^2  + a_4 \ x + a_5 \ y + a_6,\quad\text{and} \\
q(x,y) & \mydef b_1 \ x^2 + b_2 \ xy + b_3 \ y^2  + b_4 \ x + b_5 \ y + b_6,
\end{align*}

where $a_6,b_6>0$.
Let $\alpha\mydef |b_1|+\ldots+|b_5|$ and $\beta\mydef |b_1|+\ldots+|b_5|$, and let $\delta\in[0,1]$ be such that $a_6>\alpha\delta$ and $b_6>\beta\delta$.

Then for all $x,y\in [-\delta,\delta]$, we have

\begin{align}\label{lem:Core-Value:bound}
g(x,y)\in\left[\frac{-\alpha\delta+a_6}{\beta \delta+b_6},\frac{\alpha\delta+a_6}{-\beta\delta+b_6}\right].
\end{align}

In particular,

if $q(x,y)=b_6=1$ and $a_1,\ldots,a_5\in [0,c]$ for some $c\geq 0$, then

\[
\]

if $a_1,\ldots,a_5,b_1,\ldots,b_5\in[-c, c]$ for some $c\geq 0$ and $\delta\leq\frac{\eps b_6^2}{5c(a_6+(1+\eps)b_6)}$ for a given $\eps>0$, then

\[
g(x,y)\in [a_6/b_6-\eps,a_6/b_6+\eps].
\]

We bound each term in each polynomial from below and above and get

\begin{align*}
p(x,y) \in [ & -(|a_1|+|a_2|+|a_3|)\delta^2-(|a_4|+|a_5|)\delta+a_6,\\
& + (|a_1|+|a_2|+|a_3|)\delta^2+(|a_4|+|a_5|)\delta+a_6], \quad\text{and} \\
q(x,y) \in [ & -(|b_1|+|b_2|+|b_3|)\delta^2-(|b_4|+|b_5|)\delta+b_6, \\
& + (|b_1|+|b_2|+|b_3|)\delta^2+(|b_4|+|b_5|)\delta+b_6].
\end{align*}

Since $\delta\in[0,1]$, we have $\delta^2\leq\delta$, so that $p(x,y)\in [-\alpha\delta+a_6,\alpha\delta+a_6]$ and $q(x,y)\in[-\beta\delta+b_6,\beta\delta+b_6]$.
The bounds (<ref>) now follows since both of these intervals are positive by assumption.

For part (a), note that $\beta=0$ and $\alpha\in [0,5c]$.
For part (b), we get that

\[
\]

One can then check that if $\delta\leq\frac{\eps b_6^2}{5c(a_6+(1+\eps)b_6)}$, that range is contained in $[a_6/b_6-\eps,a_6/b_6+\eps]$.

Let $\delta_2\mydef 2^{-l}$ for $l\geq 3$, and let $\delta_1\mydef 2^{-l-3}$.
Consider an instance $\mathcal I_1\mydef[\Phi_1,\delta_1]$.
We can in $O(|\mathcal I_1|)=O(|\Phi_1| +l)$ time compute an instance $\mathcal I_2$ of the problem with $\delta(\mathcal I_2)=\delta_2$ and formula $\Phi_2\mydef\Phi(\mathcal I_2)$ such that
$V(\Phi_1) \simeq V(\Phi_2)$ and
$V(\Phi_1) \leqlin V(\Phi_2)$.

In the following, we specify the variables and constraints we add to $\Phi_2$.
Define $\Delta\mydef 1-\delta_1$.
As a first step, we construct constant variables $\const{c}$ for each of $c\in\{1/2, 3/4, 1, 3/2\}$, as follows.
We first use the constraint $\const{1}\cdot\const{1}=\const{1}$.
Note that the solutions to this are $\const{1}\in\{0,1\}$, but since we are restricted to $[1/2,2]$, we conclude that $\const{1}=1$.
We observe that $\const{1}$ is in the promised range $[1-\delta_2,1+\delta_2]$ of variables involved in multiplication constraints.

We can then construct the other constants as follows.

\begin{align*}
\const{1/2} + \const{1/2} & = \const{1} \\
\const{1}+\const{1/2} & = \const{3/2} \\
\const{3/4} + \const{3/4} & = \const{3/2}
\end{align*}

We now show how to construct a constant variable $\const{\Delta}$.
To this end, we construct constant variables $\const{1-2^{-i}}$ for $i\in\{1,\ldots,l\}$, so that $\const{\Delta}$ is a synonym for $\const{1-2^{-l}}$.
For the base case $i=1$, note that this is just the already constructed $\const{1/2}$.
Suppose inductively that we have constructed the constant variable $\const{1- 2^{-i}}$.
In order to construct $\const{1-2^{-(i+1)}}$, we proceed as follows.

\begin{align*}
\const{1- 2^{-i}} + \const{1} & = \const{2- 2^{-i}} \\
\const{1-2^{-(i+1)}}+\const{1-2^{-(i+1)}} & = \const{2- 2^{-i}}
\end{align*}

Thus we can generate a variable with the value $\const{\Delta}$ in $O(l)$ steps.

For each of the constant variables $\const{c}$ thus created, we define $I(\const{c})\mydef [c-\delta_2,c+\delta_2]\cap[1/2,2]$.
Note that it follows from the constraints that in any solution to $\Phi_2$, we must have $\const{c}=c$.

For each each variable $x \in [-\delta_1,\delta_1]$ of $\Phi_1$, we make a corresponding variable $\const{x+1}$ of $\Phi_2$.
As we shall see, for every solution $\mathbf x\mydef (x_1,\ldots,x_n)$ of $\Phi_1$, there will be a corresponding solution to $\Phi_2$ with $\const{x_i+1}=x_i+1$, and vice versa.

For each variable $x$ of $\Phi_1$, we construct the variables $\const{x+3/2}$, $\const{x+3/4}$, and $\const{x+\Delta}$ as follows.

\begin{align*}
\const{x+1} + \const{1/2} & = \const{x+3/2}\\
\const{x+3/4}+\const{3/4} & = \const{x+3/2}\\
\const{x+3/4} + \const{\Delta} & = \const{x+3/4+\Delta} \\
\const{x+\Delta}+\const{3/4} & = \const{x+3/4+\Delta}.
\end{align*}

For each of these of the form $\const{x+b}$, $b\in\{3/4,\Delta,3/2\}$, it holds that if $\const{x+1}=x+1$, then $\const{x+b}=x+b$.

We now go through the constraints of $\Phi_1$ and create equivalent constraints in $\Phi_2$.
For each equation $x=\delta_1$ of $\Phi_1$, we add the equation

to $\Phi_2$.
The equation implies that if $\const{x+1}=x+1$, then $x=\delta_1$.

For each equation $x+y=z$ of $\Phi_1$, we add

\begin{align}\label{etrshift:addition}
\const{x+3/4} + \const{y+3/4} = \const{z+3/2}
\end{align}

to $\Phi_2$.
This equation implies that if $\const{x+1}=x+1$ and $\const{y+1}=y+1$, then $\const{z+1}=x+y+1$.

For each equation $x \cdot y=z$ of $\Phi_1$, we have the following set of equations in $\Phi_2$.

\begin{align*}
\const{x+1} \cdot \const{y+1} &= \const{xy + x+y+1} \\
\const{xy + x + y + 1}+\const{1/2} & =\const{xy + x+y+3/2} \\
\const{xy+x+3/4} + \const{y+3/4}  &= \const{xy + x + y + 3/2}  \\
\const{xy+x+3/4}+\const{3/4} & = \const{xy+x+3/2} \\
\const{z+3/4} + \const{x+3/4}  &= \const{xy+x+3/2}
\end{align*}

These equations imply that if $\const{x+1}=x+1$ and $\const{y+1}=y+1$, then $\const{z+1}=xy+1$.

At last, for each constraint $x\geq 0$ of $\Phi_1$, we introduce the variable $\const{x+1/2}$ of $\Phi_2$ and the equation $\const{x+1/2} + \const{1/2} = \const{x+1}$.
The constraint $\const{x+1/2} \geq 1/2$, which holds for all variables of $\Phi_2$ by definition of , then corresponds to $x \geq 0$.

For the variables $\const{x+\Delta}$, we define $I(\const{x+\Delta})\mydef [1-\delta_2,1+\delta_2]$, since the variable takes part in a multiplication constraint.
For all the other variables, we define the intervals as follows.
Note that each of the introduced variables has the form $\const{p(x,y)}$, where $p(x,y)$ is a polynomial of degree at most $2$ and with constant term $c\mydef p(0,0)\in \{1/2,3/4,1,3/2\}$.
We now define $I(\const{p(x,y)})\mydef [c-\delta_2,c+\delta_2]\cap[1/2,2]$.

The construction of $\Phi_2$ is now finished, and we need to check that it has the claimed properties.
Let the variables of $\Phi_1$ be $x_1,\ldots,x_n$ and the variables of $\Phi_2$ be

For each variable $\const{y_i}$, $i\in\{1,\ldots,m\}$, the expression $y_i$ is a polynomial of degree at most two in two variables among $x_1,\ldots,x_n$ (this includes the case that $y_i$ is a constant).
Consider any solution $\mathbf x\mydef (x_1,\ldots,x_n)\in [-\delta_1,\delta_1]^n$ to $\Phi_1$.
We get a corresponding solution $f(\mathbf x)$ to $\Phi_2$ as follows.
We set $\const{x_i+1}\mydef x_i+1$ for every $i\in\{1,\ldots,n\}$.
For every $i\in\{1,\ldots,m\}$, $y_i$ is a (possibly constant) polynomial in two variables among $x_1,\ldots,x_n$, and we assign $\const{y_i}$ the value we get when evaluating this polynomial.

In order to show that this yields a solution to $\Phi_2$, we consider the constraint (<ref>) introduced to $\Phi_2$ due to an addition $x+y=z$ of $\Phi_1$.
The other constraints can be verified in a similar way.
Due to the construction of $\const{x+3/4}$, it follows from $\const{x+1}\mydef x+1$ that $\const{x+3/4}=x+3/4$, and similarly that $\const{y+3/4}=y+3/4$ and $\const{z+3/2}=z+3/2$.
Hence we have

\begin{align*}
\const{x+3/4}+\const{y+3/4}=x+3/4+y+3/4=z+3/2=\const{z+3/2},
\end{align*}

so indeed the constraint is satisfied.

Note that the inverse of $f$ is

\[
f^{-1} : (\const{x_1+1},\ldots,\const{x_n+1},\const{y_1},\ldots,\const{y_m})\mapsto (\const{x_1+1}-1,\ldots,\const{x_n+1}-1).
\]

We now show that $f^{-1}$ is a map from $V(\Phi_2)$ to $V(\Phi_1)$, i.e., that given any solution to $\Phi_2$, $f^{-1}$ yields a solution to $\Phi_1$.
Consider a constraint of $\Phi_1$ of the form $x+y=z$.
We then have

\begin{align*}
x+y & =\const{x+1}-1+\const{y+1}-1=\const{x+3/4}+1/4-1+\const{y+3/4}+1/4-1 \\
& =\const{z+3/2}-3/2=z.
\end{align*}

In a similar way, the other constraints of $\Phi_1$ can be shown to hold due to the constraints of $\Phi_2$.

It follows that $f$ is a rational homeomorphism so $V(\Phi_1)\simeq V(\Phi_2)$, and since $f^{-1}$ merely subtracts $1$ from some variables, we also have $V(\Phi_1)\leqlin V(\Phi_2)$.

At last, we need to verify that $\Phi_2$ satisfies the promise that in every solution, each variable $\const{p(x,y)}$ is in the interval $I(\const{p(x,y)})$.
Here, $p(x,y)$ is a polynomial of degree at most $2$ and with constant term $c\mydef p(0,0)\in \{1/2,3/4,1,3/2\}$.
By the map $f^{-1}$, we get a solution to $\Phi_1$ by the assignments $x\mydef \const{x+1}-1$ and $y\mydef \const{y+1}-1$ (and similarly for the remaining variables of $\Phi_1$).
It then follows from the constraints of $\Phi_2$ that $\const{p(x,y)}=p(x,y)$.
By the promise of $\Phi_1$, we get that $x,y\in[-\delta_1,\delta_1]$.
The coefficients of the non-constant terms of $p(x,y)$ are all either $0$ or $1$.
We therefore get by Lemma <ref> that since $x,y\in[-\delta_1,\delta_1]$, then $p(x,y)\in[c-5\delta_1,c+5\delta_1]\subset[c-\delta_2,c+\delta_2]$.

Recall that $I(\const{p(x,y)})\mydef [c-\delta_2,c+\delta_2]\cap[1/2,2]$ and that $\delta_2< 1/4$.
With the exception of the case $c=1/2$, we therefore have that $I(\const{p(x,y)})=[c-\delta_2,c+\delta_2]$, so it follows that $\const{p(x,y)}\in I(\const{p(x,y)})$.
Note that the case $c=1/2$ only occurs when $p(x,y)=x+1/2$ and $I(\const{x+1/2})= [1/2,1/2+\delta_2]$.
In this case, there is a constraint $x\geq 0$ in $\Phi_1$.
Hence $x\in [0,\delta_1]$, so that $\const{x+1/2}=x+1/2\in[1/2,1/2+\delta_1]\subset [1/2,1/2+\delta_2]=I(\const{x+1/2})$.

In order to construct $\const{\Delta}$ in $\Phi_2$, we introduce $O(l)$ variables and constraints.
For each of the $O(|\Phi_1|)$ variables and constraints of $\Phi_1$, we make a constant number of variables and constraints in $\Phi_2$.
It thus follows that the running time is $O(|\Phi_1|+l)$.
This completes the proof.

§.§ Reduction to

In this and the following section, we show that the problem remains essentially equally hard even when we only allow more specialized types of multiplications in our formulas.
In this section, we require every multiplication to be a squaring of the form $x^2=y$, and in the following section, we only allow inversion of the form $x\cdot y=1$.
The result that these two restricted types of constraints preserve the full expressibility of is related to the result of Aho  <cit.> that squaring and taking reciprocals of integers require work proportional to that of multiplication.

An formula $\Phi\mydef \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

\begin{align*}
x+y=z,\quad x^2=y
\end{align*}

for $x,y,z \in \{x_1, \ldots, x_n\}$.

An instance $\mathcal I=\left[\Phi,\delta,(I(x_1),\ldots,I(x_n))\right]$ of the problem is an formula $\Phi$, a number $\delta\mydef 2^{-l}$ for a positive integer $l$, and, for each variable $x\in\{x_1,\ldots,x_n\}$, an interval $I(x)\subseteq [1/2,2]$ such that $|I(x)|\leq 2 \delta$.
For every squaring constraint $x^2=y$, we have $I(x)\subset [1-\delta,1+\delta]$.

We are promised that $V(\Phi)\subset I(x_1)\times\cdots\times I(x_n)$.
The goal is to decide whether $V(\Phi)\neq\emptyset$.

Below, we present a reduction from the problem to .

Let $\delta_2\mydef 2^{-l}$ be given for $l\geq 3$, and let $\delta_1\mydef 2^{-l-4}$.
Consider an instance $\mathcal I_1$ of the problem such that $\delta(\mathcal I_1)=\delta_1$, and let $\Phi_1\mydef\Phi(\mathcal I_1)$.
We can in $O(|\mathcal I_1|)$ time compute an instance $\mathcal I_2$ of the problem with $\delta(\mathcal I_2)=\delta_2$ and formula $\Phi_2\mydef\Phi(\mathcal I_2)$ such that
$V(\Phi_1) \simeq V(\Phi_2)$ and
$V(\Phi_1) \leqlin V(\Phi_2)$.

As in the proof of Lemma <ref>, we first construct constant variables $\const{b}$ for each of $b\in\{1/2, 3/4, 1, 3/2\}$.
The only difference is that we now construct $\const{1}$ using the constraint $\const{1}^2=\const{1}$.
The other constants are then constructed in exactly the same way as before.

We include each variable $x$ of $\Phi_1$ in $\Phi_2$ as well, and reuse the interval $I(x)$ from $\mathcal I_1$ in $\mathcal I_2$.
We also reuse all contraints from $\Phi_1$ of the form $a+b=c$ in $\Phi_2$, but we have to do something different for the constraints $a\cdot b=c$.
The idea is very simple and was also used by Aho  <cit.>, and can be expressed by the equations

\begin{align*}
x &= (a+b)/2\\
y &= (a-b)/2\\
u &= x^2 \\
v &= y^2 \\
c &= u-v = a\cdot b.
\end{align*}

If there were no range constraints, we could just replace each multiplication $a\cdot b =c$ of $\Phi_1$ by equations as above (after rewriting the subtractions as additions, etc.).
However, in our situation all
intermediate variables $w$ need to
be in a range $I(w)\subset [1/2,2]$ in any solution.
While this makes the description more involved, careful shifting will work for us.

Let $a\cdot b =c$ be a multiplication constraint in $\Phi_1$.
Let us rename the variables as $\const{x+1}\mydef a$, $\const{y+1}\mydef b$, and $\const{xy+x+y+1}\mydef c$, so that $a\cdot b =c$ becomes

\begin{align}
\label{etrsquare:mult}
\const{x+1}\cdot\const{y+1}=\const{xy+x+y+1}.\tag{$\dagger$}
\end{align}

Consider two numbers $x,y\in\R$ and the two conditions

\begin{align}
& \const{x+1}=x+1\quad\text{and}\quad \const{y+1}=y+1,\label{etrsquare:cond}\tag{$\star$} \\
& \const{xy+x+y+1} =xy+x+y+1.\label{etrsquare:cond2}\tag{$\star\star$}
\end{align}

We claim that (<ref>) is equivalent to

\begin{align}
\text{\eqref{etrsquare:cond} implies \eqref{etrsquare:cond2}}.\label{etrsquare:cond3}\tag{$\ddagger$}
\end{align}

To show this claim, suppose first that (<ref>) holds.
Define $x\mydef\const{x+1}-1$ and $y\mydef\const{y+1}-1$.
Then $\const{xy+x+y+1}=\const{x+1}\cdot\const{y+1}=(x+1)\cdot (y+1)=xy+x+y+1$, so that (<ref>) holds.
Hence we have (<ref>).
On the other hand, suppose that (<ref>) holds, and define $x\mydef\const{x+1}-1$ and $y\mydef\const{y+1}-1$ so that (<ref>) holds.
Our assumption implies that (<ref>) holds, and we thus have $\const{xy+x+y+1}=xy+x+y+1=(x+1)\cdot(y+1)=\const{x+1}\cdot\const{y+1}$, so that (<ref>) holds.
Our aim is therefore to make constraints in $\Phi_2$ that ensure (<ref>).

For every variable $\const{q}$ of $\Phi_2$, we can construct $\const{q/2}$ using the constraint $\const{q/2} + \const{q/2} = \const{q}$.
Similarly, we can construct $\const{2q}$ by $\const{q} + \const{q} = \const{2q}$.

The construction of $\const{xy+x+y+1}$ is shown in Figure <ref>.
The diagram should be understood in the following way.
We start with the original variables $\const{x+1}$ and $\const{y+1}$.
Each arrow is labeled with the operation that leads to the new variable.
It is straightforward to check that the construction ensures condition (<ref>).

Note that each of the constructed auxilliary variables has the form $\const{p(x,y)}$, where $p(x,y)$ is a second degree polynomial with constant term $c\mydef p(0,0)\in\{3/4,1,3/2\}$.
We define $I(\const{p(x,y)})\mydef [c-\delta_2,c+\delta_2]$.
This finishes the construction of $\mathcal I_2$.
Note that since $\delta_2\leq 1/4$ and $c\in\{3/4,1,3/2\}$, we get that $I(\const{p(x,y)})\subset[1/2,2]$, as required.

We now verify that $\mathcal I_2$ has the claimed properties.
Consider a solution $\mathbf x\in V(\Phi_1)$.
We point out an equivalent solution to $\Phi_2$.
For all the variables of $\Phi_2$ that also appear in $\Phi_1$, we use the same value as in the solution $\mathbf x$.
Each auxilliary variable has the form $\const{p(x,y)}$, where $p(x,y)$ is a second degree polynomial, and $\Phi_1$ contains the multiplication constraint (<ref>).
We then get from the promise of $\Phi_1$ that $\const{1+x}=1+x$ and $\const{1+y}=1+y$ for $x,y\in[-\delta_1,\delta_1]$.
From the construction shown in Figure <ref>, it follows that in order to get a solution to $\Phi_2$, we must define $\const{p(x,y)}\mydef p(x,y)$.
Recall that the constant term $c\mydef p(0,0)$ satisfies $c\in \{3/4,1,3/2\}$, and note that all the coefficients of the non-constant terms of $p(x,y)$ are in the interval $[0,2]$.
We then get from Lemma <ref> that $\const{p(x,y)}\in[c-10\delta_1,c+10\delta_1]=[c-\delta_2,c+\delta_2]=I(\const{p(x,y)})\subset[1/2,2]$.
The variables are thus in the range $[1/2,2]$, so we have described a solution to $\Phi_2$.

Similarly, we see that any solution to $\Phi_2$ corresponds to a solution to $\Phi_1$.
Using the promise of $\mathcal I_1$ and Lemma <ref> as above, we then also confirm the promise of $\mathcal I_2$ that each variable $u$ of $\Phi_2$ is in $I(u)$.

The construction of $\const{xy+x+y+1}$ from $\const{x+1}$ and $\const{y+1}$.
Squaring a variable is denoted by $^\wedge 2$.

The correspondance described implies that $V(\Phi_1)\simeq V(\Phi_2)$ and $V(\Phi_1)\leqlin V(\Phi_2)$.
For each constraint of $\Phi_1$, we introduce $O(1)$ variables and constraints of $\Phi_2$, so the reduction takes $O(|\Phi_1|)$ time.

§.§ Reduction to

We will now present a reduction
from the problem to .

Let $\delta_2\mydef 2^{-l}$ be given for $l\geq 3$, and let $\delta_1\mydef 2^{-l-11}$.
Consider an instance $\mathcal I_1$ of the problem such that $\delta(\mathcal I_1)=\delta_1$, and let $\Phi_1\mydef\Phi(\mathcal I_1)$.
We can in $O(|\mathcal I_1|)$ time compute an instance $\mathcal I_2$ of the problem with $\delta(\mathcal I_2)=\delta_2$ and formula $\Phi_2\mydef\Phi(\mathcal I_2)$ such that
$V(\Phi_1) \simeq V(\Phi_2)$ and
$V(\Phi_1) \leqlin V(\Phi_2)$.

As in the proof of Lemma <ref>, we first construct constant variables $\const{b}$ for each of $b\in\{1/2, 3/4, 1, 3/2\}$.
The only difference is that we now construct $\const{1}$ using the constraint $\const{1}\cdot\const{1}=1$.
It follows from this constraint that $\const{1}\in\{-1,1\}$, and since $\const{1}\in[1/2,2]$, we must have $\const{1}=1$ in every valid solution.
The other constants are then constructed in exactly the same way as before.
For this reduction we also need the constant variable $\const{2/3}$ which is constructed as $\const{2/3}\cdot \const{3/2} = 1$.

We include each variable $x$ of $\Phi_1$ in $\Phi_2$ as well, and reuse the interval $I(x)$ from $\mathcal I_1$ in $\mathcal I_2$.
We also reuse all contraints from $\Phi_1$ of the form $a+b=c$ in $\Phi_2$, but we have to do something different for the squaring constraints $a^2=b$.
In $\Phi_2$, we rename the variables as $\const{x+1}\mydef a$ and $\const{x^2+2x+1}\mydef b$, so that $a^2 =b$ becomes

\begin{align}
\label{etrinv:sqr}
\const{x+1}^2=\const{x^2+2x+1}.\tag{$\dagger$}
\end{align}

Consider a number $x\in\R$ and the two conditions

\begin{align}
& \const{x+1}=x+1,\label{etrinv:cond}\tag{$\star$} \\
& \const{x^2+2x+1}=x^2+2x+1.\label{etrinv:cond2}\tag{$\star\star$}
\end{align}

As in the proof of Lemma <ref>, one can prove that (<ref>) is equivalent to

\begin{align}
\text{\eqref{etrinv:cond} implies \eqref{etrinv:cond2}}.\label{etrinv:cond3}\tag{$\ddagger$}
\end{align}

Our aim is therefore to make constraints in $\Phi_2$ that ensure (<ref>).

In the same way as described in Section <ref>
and Section <ref>, we can add values, subtract values,
half and double variables.
Figure <ref> shows the construction of $\const{x^2+2x+1}$ using these tricks as well as inversions.
It is straightforward to check that the construction ensures condition (<ref>).

The sequence above enforces $ y = x^2$, using only addition and inversion.
Inversion is denoted by $\setminus 1$.

For all the variables $x$ of $\Phi_2$ that also appear in $\Phi_1$, we define the interval $I(x)$ in $\mathcal I_2$ as it is in $\mathcal I_1$.
Each of the auxilliary variables has the form $\const{\frac{p(x)}{q(x)}}$, where $p(x)$ and $q(x)$ are polynomials of degree $2$.
We define $c\mydef \frac{p(0)}{q(0)}$ and note that $c\in[2/3,7/4]$.
We define $I\left(\const{\frac{p(x)}{q(x)}}\right)\mydef [c-\delta_2,c+\delta_2]$.
This finishes the construction of $\mathcal I_2$.
Note that since $\delta_2\leq 1/6$ and $c\in[2/3,7/4]$, we get that $I\left(\const{\frac{p(x)}{q(x)}}\right)\subset[1/2,2]$.

We now verify that $\mathcal I_2$ has the claimed properties.
Consider a solution $\mathbf x\in V(\Phi_1)$.
For all the variables of $\Phi_2$ that also appear in $\Phi_1$, we use the same value as in the solution $\mathbf x$.
Each auxilliary variable has the form $\const{\frac{p(x)}{q(x)}}$, where $p(x)$ and $q(x)$ are polynomials of degree $2$, and $\Phi_1$ contains the squaring constraint (<ref>).
We then get from the promise of $\Phi_1$ that $\const{1+x}=1+x$ for $x\in[-\delta_1,\delta_1]$.
From the construction shown in Figure <ref>, it follows in order to get a solution to $\Phi_2$, we must define $\const{\frac{p(x)}{q(x)}}\mydef \frac{p(x)}{q(x)}$.
We are going to apply case (b) of Lemma <ref> to show that this solution stays in the required range $[1/2,2]$.
The coefficients of the non-constant terms of $p(x)$ and $q(x)$ are in the range $[-1,15]$.
Denote by $a_6$ and $b_6$ the constant terms of $p(x)$ and $q(x)$, respectively.
We observe that $b_6^2\geq 1$ and $a_6+(1+\delta_2)b_6\leq 6+2\cdot 9=24$.
We therefore get that since $\delta_1< \delta_2/1800=\frac{\delta_2}{5\cdot 15\cdot 24}<\frac{\delta_2 b_6^2}{5\cdot 15(a_6+(1+\delta_2)b_6)}$, then $\const{\frac{p(x)}{q(x)}}\in [c-\delta_2,c+\delta_2]\subset[1/2,2]$.

Similarly, we see that any solution to $\Phi_2$ corresponds to a solution to $\Phi_1$.
Using the promise of $\mathcal I_1$ and Lemma <ref> as above, we then also confirm the promise of $\mathcal I_2$ that each variable $u$ of $\Phi_2$ is in $I(u)$.

The correspondance described implies that $V(\Phi_1)\simeq V(\Phi_2)$ and $V(\Phi_1)\leqlin V(\Phi_2)$.
For each constraint of $\Phi_1$, we introduce $O(1)$ variables and constraints of $\Phi_2$, so the reduction takes $O(|\Phi_1|)$ time.

We can now prove Theorem <ref>.

That is -complete follows from Lemmata <ref>–<ref>.
That this holds even when $\delta=O(n^{-c})$ follows from Corollary <ref> and Lemmata <ref>–<ref>.
For a given instance $\Phi$ of where $V(\Phi)$ is compact, all the reductions preserve rational equivalence and result in linear extensions.
Hence the final claim.

§.§ Reduction to

In our reduction to packing problems, we reduce from an auxilliary problem called .
An instance of is an instance of together with a graphical representation of the formula $\Phi$, i.e., a drawing of $\Phi$ of a specific form, which we call a wiring diagram; see Figure <ref>.

The term “wiring diagram” is often used about drawings of a similar appearance used to represent electrical circuits
or pseudoline arrangements.
We define equidistant horizontal diagram lines $\ell_1,\ldots,\ell_{2n}$ so that $\ell_1$ is the topmost one and $\ell_{2n}$ is bottommost.
The distance between consecutive lines is $10$.
In a wiring diagram, each variable $x_i$ in $\Phi$ is represented by two $x$-monotone polygonal curves $\overrightarrow{x_i}$ and $\overleftarrow{x_i}$, which we call wires.
We think of $\overrightarrow{x_i}$ as oriented to the right and $\overleftarrow{x_i}$ as oriented to the left.
The wire $\overrightarrow{x_i}$ starts and ends on $\ell_{2i-1}$, and $\overleftarrow{x_i}$ starts and ends on $\ell_{2i}$.
Each wire consists of horizontal segments contained in the diagram lines and jump segments, which are line segments connecting one diagram line $\ell_j$ to a neighbouring diagram line $\ell_{j\pm 1}$.
The wires are disjoint except that each jump segment must cross exactly one other jump segment.
Thus, the jump segments are used when two wires following neighbouring diagram lines swap lines.

The left and right endpoints of $\overrightarrow{x_i}$ and $\overleftarrow{x_i}$ are vertically aligned, and the wires appear and disappear in the order $(\overrightarrow{x_1},\overleftarrow{x_1}),\ldots,(\overrightarrow{x_n},\overleftarrow{x_n})$ from left to right in a staircase-like fashion.

In the wiring diagram, we represent each constraint of $\Phi$ as two inequalities, i.e., $x_i+x_j=x_k$ becomes $x_i+x_j\leq x_k$ and $x_i+x_j\geq x_k$ and $x_i\cdot x_j=1$ becomes $x_i\cdot x_j\leq 1$ and $x_i\cdot x_j\geq 1$.
Each inequality is represented by an axis-parallel constraint box intersecting the three or two topmost diagram lines; three for addition constraints and two for inversion constraints.
These boxes are pairwise disjoint.
For a constraint $x_i+x_j\leq x_k$, the right-oriented wires $\overrightarrow{x_i},\overrightarrow{x_j},\overrightarrow{x_k}$ must inside the box occupy the lines $\ell_1,\ell_2,\ell_3$, respectively.
For $x_i+x_j\geq x_k$, we need the left-oriented wires $\overleftarrow{x_i},\overleftarrow{x_j},\overleftarrow{x_k}$ instead.
For the inversion inequalities $x_i\cdot x_j\leq 1$ and $x_i\cdot x_j\geq 1$, we need one of the wires of $x_i$ and one of the wires of $x_j$ to occupy $\ell_1$ and $\ell_2$.
Which combination and which order depends on the particular variant of packing that we are reducing to.

Each vertical line is allowed to cross either zero or two jump segments and in the latter case, these two must cross each other.
A vertical line crossing a constraint box must not cross any jump segment.

A wiring diagram corresponding to the formula $x_2+x_3=x_1\land x_1\cdot x_2=1$.

An instance $\mathcal I\mydef[\mathcal I',D]$ of the problem consists of an instance $\mathcal I'$ of together with a wiring diagram $D$ of the formula $\Phi(\mathcal I')$.

Given an formula $\Phi$ with variables $x_1,\ldots,x_n$, we can in $O(n^4)$ time construct a wiring diagram of $\Phi$.

We may assume that $\Phi$ has $O(n^3)$ constraints, since there will otherwise be dublicates of some constraints.
We construct a wiring diagram as follows; refer to Figure <ref>.
We construct all the curves simultaneously from left to right, so that the $x$-coordinates of their left endpoints are all identical, as are the $x$-coordinates of their right endpoints.
We handle the constraints in order and define the curves as we go along.
For instance, for a constraint such as $x_i+x_j\leq x_k$, we route $\overrightarrow{x_i}$ to the line $\ell_1$ using jump segments.
This defines how all other curves should behave in the same range of $x$-coordinates where we have routed $\overrightarrow{x_i}$.
We then route $\overrightarrow{x_j}$ to the line $\ell_2$, and then route $\overrightarrow{x_k}$ to $\ell_3$.
Each time we route a curve to a specific line, we introduce $O(n)$ crossings.
Therefore, we make $O(n^4)$ crossings in total.

§ FINGERPRINTING

In this section, we develop a technique to argue that pieces are roughly
at the position where we intend them to be.
The high level idea is based on a few properties.
First, the slack $\slack$, i.e., the difference between the area of the container
and the total area of the pieces, is very small.
Second, every piece $p$ has a specific corner $v$ with a unique angle that
fits precisely at one position. If we were to place another piece
there, we would create an empty space which is larger than $\slack$.

§.§ Fingerprinting a single piece

Now let us go one level deeper into the details of the technique, see also Figure <ref>.
We consider a case where we already know the position of some pieces (possibly with some uncertainty), and we consider the empty space $E$ where the remaining pieces must be placed.
Ideally, we could identify a corner $w$ of the empty space and a corner $v$ of a remaining piece $p$ which has exactly the same angle as $w$ and deduce that $p$ must be placed with $v$ at $w$.
Unfortunately, this is not the case, for two reasons.
First, we want to give most pieces some tiny but non-zero amount of wiggle room.
This is important as pieces are meant to represent variables.
Second, we do not know the precise position of the other pieces as previous fingerprinting steps could only infer approximate and not exact positions of those pieces.
Thus, we will identify for each piece $p$ a triangle $T$, which has a corner $y$ with the same angle as $v$.
The edges adjacent to $y$ will be very close to but not exactly on the boundary of the empty space $E$.
The triangle $T$ will be our main protagonist in the forthcoming proofs and formal definitions.
It may partially overlap existing pieces or have some distance to already placed pieces.
Another key player is the uncertainty value $\lambda\geq 0$, which is a measure of how much $T$ is off from the ideal.
We are now ready to go into the full details of the fingerprinting.

We are considering the placement of the pieces $p_1,\ldots,p_{i-1}$ according to a valid motion $\m$.
The white area is the empty space $E$ available for the remaining pieces $p_i,\ldots,p_N$.
The gray circles centered at $x,y,z$ have radius $u$.
The first must contain $a$, the second $b$ and $c$, and the third $d$ such that $ab$ and $cd$ are segments on the boundary of $E$.

We are given a container $\cont$ and pieces $\p=(p_1,\ldots,p_N)$.
Each piece $p\in\p$ is a simple polygon with the following properties.

* Each segment of $p$ has length at least $1$.

* The diameter of $p$ is at most some number $d_{\max}$.

* The polygon $p$ is fat in the following sense.
For any two points $v,w$ on different and non-neighbouring segments of $p$, we have $\|vw\|\geq \mu\mydef 1/100$.

Recall that the slack $\slack$ is the area of $\cont$ minus the total area of the pieces $\p$.

In Section <ref>, we will show that the results developed in the following for polygonal pieces also hold when the pieces are allowed to be curved polygons (provided that the curvature is sufficiently small and the curved part of each segment is sufficiently short).

The empty space $E$.
We consider an arbitrary valid motion $\m$ and analyze how we can infer something about the placement of the pieces $p_i,\ldots,p_N$ from the placement of the first $i-1$ pieces $p_1,\ldots,p_{i-1}$.
We can think of this situation as if we have already decided where to place the first $i-1$ pieces $p_1,\ldots,p_{i-1}$ in $\cont$ so that they are interior-disjoint, and we are now reasoning about where to place the next piece.

$$E\mydef \overline{\cont\setminus\bigcup_{j=1}^{i-1} \pl {p_j}\m}$$

be the uncovered space available for the remaining pieces $p_i,\ldots,p_N$, see Figure <ref>.
Then $E$ is a subset of $\cont$ bounded by a finite number of line segments.
Note that all segments on the boundary of $E$ are contained in edges of the pieces $\pl {p_1}\m,\ldots,\pl {p_{i-1}}\m$ or $\cont$.

Covering a wedge of $E$.
Assume that there is a special triangle $T\subset \cont$ with corners $x,y,z$ and with the following properties.
We have $\|xy\|=\|yz\|=1$.
Let $\lambda\geq 0$ be a (small) number that will be defined whenever we are going to apply the fingerprinting.
The value $\lambda$ can be thought of as a measure of uncertainty of the already placed pieces and the distance from the boundary of $T$ to the boundary of $E$.
Let $\inn{T}=\inn{x}\inn{y}\inn{z}$ denote the triangle $T\ominus\disk(\lambda)$, such that $\inn{x},\inn{y},\inn{z}$ are on the angular bisectors from $x,y,z$, respectively.

We say that $E$ is $\lambda$-bounding $T$ at $y$
if the following two conditions hold:

* There are segments $ab$ and $cd$ on the boundary of $E$ such that each of the distances $\|ax\|,\|by\|,\|cy\|,\|dz\|$ is at most $\lambda$.

* The interior of $\inn{T}$ is a subset of $E$.

The second requirement means that no piece among $p_1,\ldots,p_{i-1}$ covers anything of $\inn T$ when placed according to $\m$.
The triangle $\inn{T}$ will have an area much larger than $\slack$, which implies that almost all of $\inn{T}$ must be covered by the pieces $\pl {p_i}\m,\ldots,\pl {p_N}\m$.

Unique angle property.
We assume that the pieces $p_i,\ldots,p_N$ have the following property, which we denote as the unique angle property.
Let $\beta$ be the interior angle of $T$ at $y$.
We require that $\beta \in[\alpha_{\min},\pi/2]$, where $\alpha_{\min}\mydef 5\pi/180$.

For the a (small) number $\sigma$, we require the following.
Consider any set $S\mydef \{v_1,\ldots,v_m\}$ of at most one corner from each piece $p_i,\ldots,p_N$.
If the sum of angles of corners in $S$ is in the interval $[\beta-\sigma,\beta+\sigma]$, then $S$ consists of only one corner $v$, i.e., $S=\{v\}$.

In most applications of the fingerprinting technique, there will be only one such set $S=\{v\}$.
In other words, the angle range $[\beta-\sigma,\beta+\sigma]$ uniquely identifies a specific piece and a specific corner $v$ of the piece.
However, in Section <ref>, we are going to consider a special case where the container is a square where there will be more such sets.

We will argue that almost all of $\inn{T}$ must be covered by a piece with a corner $v$ with an angle in the range $[\beta-\sigma,\beta+\sigma]$, and the corner $v$ must be placed close to $y$.
Informally, since $\slack$ is much smaller than the area of $\inn T$, almost all of $\inn T$ must be covered by the pieces $p_i,\ldots,p_N$.
Because of the unique angle property, it is only possible to cover a sufficient amount of $\inn T$ by placing a piece with such a corner $v$ close to $y$ and with the adjacent edges close to parallel to $yx$ and $yz$, since the edges $ab$ and $cd$ of $\partial E$ are preventing $\inn T$ to be covered in another way.

Main lemma.
To sum up, we have made these assumptions:

* We consider a valid placement $\m$ of the pieces $\p$.

* The empty space $E$ is $\lambda$-bounding the triangle $T$ at the corner $y$ of $T$.

* The pieces $p_i,\ldots,p_N$ have the unique angle property with respect to the angle $\beta$ of the corner $y$.

In Section <ref>, we are going to prove the following lemma in the setting described above.

There is a piece $p \in\{p_i,\ldots,p_N\}$, with a corner $v$ such that the angle of $v$ is in $[\beta-\sigma,\beta+\sigma]$ and
$\|y\pl {v}\m\|= O\left(\lambda/\sigma+\sqrt{\slack/\sigma}\right)$.

Furthermore, let $u,w$ be the corners preceding and succeeding $v$, respectively.
Then the angle between $\pl {v}\m\pl {u}\m$ and $yx$ is
as is the angle between $\pl {v}\m\pl {w}\m$ and $yz$.

§.§ Fingerprinting more pieces at once

In this section, we consider the iterated use of the finger printing technique (in particular Lemma <ref>) for some number of times.
This describes the situation whenever we have introduced the pieces of a new gadget to the construction.
More precisely, we consider the situation where we know how the pieces $p_1,\ldots,p_{i-1}$ must be placed, and we want to deduce how the following $k$ pieces $p_i,\ldots,p_{i+k-1}$, for some $k\geq 1$, must then be placed.
To this end, consider an arbitrary valid motion $\m$.
For each $j\in\{1,\ldots,i-1\}$, define the motion $s_j\mydef m_j$.
Consider a set of intended motions $s_i,\ldots,s_{i+k-1}$ of the pieces $p_i,\ldots,p_{i+k-1}$.
We are going to define what it means for the intended motions to be sound, and then we prove that if they are sound, then the valid motion $\m$ must place the pieces $p_i,\ldots,p_{i+k-1}$ in a way similar to the intended motions.

To define soundness of the intended motions, we first define the empty space $E^\s_j$ as

$$E^\s_j\mydef \overline{\cont\setminus\bigcup_{l=1}^{j-1} \pl {p_l}{s_l}}.$$

We say that the intended motion $s_j$, $j\in\{i,\ldots,i+k-1\}$, is $\lambda$-sound, for a value $\lambda\geq 0$, if exists a triangle $T_j=x_jy_jz_j$ and a corner $v_j$ of $p_j$ such that the following holds.

* the angle $\beta_j$ of $T_j$ at $y_j$ is in the range $[\alpha_{\min},\pi/2]$,

* $\|x_jy_j\|= 1$ and $\|y_jz_j\|= 1$,

* $E^\s_j$ is $\lambda$-bounding $T_j$ at $y_j$
(recall Definition <ref>),

* the following stronger version of the unique angle property holds:
among all corners of all pieces $p_j,\ldots,p_N$, only the corner $v_j$ of $p_j$ has an angle in the range $[\beta_j-\sigma,\beta_j+\sigma]$.

* $T_j\subset \pl {p_j}{s_j}$,

* $\pl {v_j}{s_j}=y_j$ and $x_jy_j,y_jz_j\subset\partial \pl {p_j}{s_j}$.

We likewise define the placement $\pl {p_j}{s_j}$ to be $\lambda$-sound if the motion $s_j$ is $\lambda$-sound.

There exists an absolute constant $c>0$ such that the following holds.

\begin{align*}
\Lambda_i & \mydef 0,\quad\text{and} \\
\Lambda_j & \mydef cd_{\max}/\sigma\cdot \Lambda_{j-1}+cd_{\max}(\lambda/\sigma+\sqrt{\slack/\sigma}),
\end{align*}

for $j>i$.
If the motions $s_i,\ldots,s_{i+k-1}$ are $\lambda$-sound, then for each $j\in\{i,\ldots,i+k-1\}$, the displacement between $m_j$ and $s_j$ is at most $\Lambda_{j+1}$.
It holds that

$$\Lambda_{k+1}\leq (k+1) (cd_{\max}/\sigma)^{k+1}(\lambda/\sigma+\sqrt{\slack/\sigma}),$$

which is a bound on all the mentioned displacements.

We proceed by induction on $j$.
For $j=i$, we apply Lemma <ref>.
We get that
$\|y_i\pl {v_i}\m\|\leq O\left(\lambda/\sigma+\sqrt{\slack/\sigma}\right)$.
Furthermore, the second half of the lemma implies that the displacement angle between the motions $m_i$ and $s_i$ is likewise $O\left(\lambda/\sigma+\sqrt{\slack/\sigma}\right)$.
We therefore get that the displacement between $m_i$ and $s_i$ is

for some constant $c$.

Suppose now that the statement holds for indices $i,i+1,\ldots,j-1$.

$$E^\m_j\mydef \overline{\cont\setminus\bigcup_{l=1}^{j-1} \pl {p_l}{m_l}}.$$

Since $E^\s_j$ is $\lambda$-bounding $T_j$ at $y_j$ and the displacement between $m_{j-1}$ and $s_{j-1}$ is at most $\Lambda_j$, we get that $E^\m_j$ is $(\Lambda_j+\lambda)$-bounding $T_j$ at $y_j$.
Therefore, Lemma <ref> gives that the displacement between $m_j$ and $s_j$ is at most

cd_{\max}((\Lambda_j+\lambda)/\sigma+\sqrt{\slack/\sigma})=cd_{\max}/\sigma\cdot \Lambda_j+cd_{\max}(\lambda/\sigma+\sqrt{\slack/\sigma})=\Lambda_{j+1},

for the constant $c$ introduced above.
Unfolding the expression, we get

\begin{align*}
\Lambda_{k+1} & =\sum_{j=0}^k (cd_{\max}/\sigma)^j\cdot cd_{\max}(\lambda/\sigma+\sqrt{\slack/\sigma}) \\
& \leq \sum_{j=0}^k (cd_{\max}/\sigma)^{j+1}\cdot (\lambda/\sigma+\sqrt{\slack/\sigma}) \\
& \leq (k+1) (cd_{\max}/\sigma)^{k+1}(\lambda/\sigma+\sqrt{\slack/\sigma}). \qedhere
\end{align*}

The following lemma will be used to fingerprint the pieces in each gadget individually.

Consider a gadget and its pieces $p_i,\ldots,p_{i+k-1}$, for $k\leq 7$, which are introduced in some step of the construction.
Suppose that there exists a valid motion $\m$ of the complete construction that moves the pieces $p_1,\ldots,p_{i-1}$ to a canonical placement.
Furthermore, suppose that there exists intended motions $s_i,\ldots,s_{i+k-1}$ which are $\gadgets\slack$-sound.
Then the displacement between the intended motion $s_j$ and the actual motion $m_j$ is $O(n^{-48})$.

In our construction, we have $d_{\max}=O(n^4)$, $\delta\mydef n^{-300}$, $\slack=O(\delta n^4)=O(n^{-296})$, $\sigma=\Omega(N^{-2})=\Omega(n^{-8})$, and $g=O(n^4)$, so we get from Lemma <ref> that the displacement is at most

8 (cd_{\max}/\sigma)^8(\lambda/\sigma+\sqrt{\slack/\sigma})=
O((n^4n^8)^8(n^{-292}n^8+\sqrt{n^{-296}n^8}))=O(n^{96}n^{-144})=O(n^{-48}). \qedhere

§.§ Proof of Single Fingerprint (Lemma <ref>)

Setup in the proof of Lemma <ref>.
The circles centered at $\pl x\i,\pl y\i, \pl z\i$ bound the disks of radius $\lambda$ in which the points $a,b,c,d$ are known to be.
The figure is not to scale.
In practice, $\lambda$ is very small so that the triangles $\out{T},T,\inn{T}$ are almost equally large.
Furthermore, the radius of $A_2$ is much larger than the radius of $A_1$, which in turn is much larger than the radius of $A_0$.
The right figure shows the regions $D_1$ and $D_2$, that together make up $D$.
The segments $ab$ and $cd$ are drawn with thick lines to indicate that these act as a restriction to where the next piece can be placed.

Proof setup.
See Figure <ref>.
Let $\zeta(\theta)\mydef \frac{1}{\sin (\theta/2)}$.
The function $\zeta$ is important when computing the distances between corresponding corners of offset versions of the same triangle, as the following lemma makes clear.

Consider a triangle $U=efg$ and define for some $s>0$ the triangle $\inn{U}\mydef U\ominus \disk(s)=\inn{e}\inn{f}\inn{g}$, so that $\inn{e},\inn{f},\inn{g}$ are on the angular bisectors of $e,f,g$, respectively.
Then $\|e\inn{e}\| = s \zeta(\theta)$, where $\theta$ is the angle of $U$ at $e$.

Let $e,f,g$ be points such that the distances from a point $\inn{e}$ to each of the segments $ef$ and $eg$ is at most $s$.
Then $\|e\inn{e}\|\leq s\zeta(\theta)$, where $\theta\in[0,\pi)$ is the angle between $ef$ and $eg$.

Proof of (1): Let $p$ be the projection of $\inn{e}$ on $ef$.
Then $\|e\inn e\|=\|p\inn e\|/\sin(\theta/2)=s\zeta(\theta)$.

Proof of (2): For a given angle $\theta$, the distance $\|e\inn{e}\|$ is maximum if the distances from $\inn{e}$ to each segment $ef$ and $eg$ are both $s$, so that, in particular, $\inn{e}$ is on the angular bisector between the segments $ef$ and $eg$.
We then proceed as in the proof for (1).

Lemma <ref> gives that $\|y\inn{y}\|=\lambda \zeta(\beta)$.

Let $\out{T}=\out{x}\out{y}\out{z}$ be the triangle we get by offsetting the edges of $T$ outwards in a parallel fashion by distance $\lambda\cdot \zeta(\alpha_{\min})$, i.e., $\out{T}$ is the triangle such that $\out{T}\ominus \disk(\lambda\cdot \zeta(\alpha_{\min}))=T$.
The corners $\out{x},\out{y},\out{z}$ are on the angular bisectors of $x,y,z$, respectively.

$\psi  \mydef \zeta(\alpha_{\min})+\zeta(\alpha_{\min})^2=O(1)$.
By Lemma <ref>, we have $\|y\out{y}\|=\lambda \zeta(\alpha_{\min})\zeta(\beta) \leq \lambda \zeta(\alpha_{\min})^2$, and $\|\out{y}\inn{y}\|=\lambda(\zeta(\beta)+ \zeta(\alpha_{\min})\zeta(\beta))\leq \lambda\psi$.

Subdividing $\out{T}$ by arcs.
Define three radii as

\begin{align*}
r_0 & \mydef \lambda\psi=\Omega(\lambda), \\
r_1 & \mydef \Omega\left(\lambda/\sigma+\sqrt{\slack/\sigma}\right), \\
r_2 & \mydef \Omega\left(r_1/\sigma\right).
\end{align*}

We furthermore require that $r_2$ is much smaller than $1$, say $r_2< 1/10$ (as it turns out, by choosing $\delta$ small enough, we can make $\slack$ so small that $r_2$ is below any desired constant).
For the ease of presentation, we will not specify the constants that should be chosen for $r_1$ and $r_2$, but it will follow from the analysis that constants exist that will make the arguments work.
Note that in our application Lemma <ref>, we will have $\sigma=\Theta(n^{-8})$, one should think of $r_1$ as much larger than $r_0$ and $r_2$ as much larger than $r_1$.

Let $A_i$ be the arc with center $\out{y}$ and radius $r_i$ from the point $\out{s_i}$ on segment $\out{y}\out{z}$ counterclockwise to the point $\out{t_i}$ on segment $\out{x}\out{y}$.

Let $D$ be the region bounded by segments $\out{t_2}\out{y}$ and $\out{y}\out{s_2}$ and the arc $A_2$.
The arc $A_1$ separates $D$ into two regions $D_1$ and $D_2$, where $A_2$ appears on the boundary of $D_2$.

Top left: The setup of Lemma <ref>.
Top right: In the shown example, $\beta_i=\gamma_i-\alpha_s+\alpha_t$.
Since $\alpha_s=O(r_1/r_2)$ and $\alpha_t=O(r_1/r_2)$, we always have $\beta_i=[\gamma_i-O(r_1/r_2),\gamma_i+O(r_1/r_2)]$.
Bottom: The angle $\theta$ is an argument of the segment $y_iw$.
The argument is bounded by $\beta+O(r_1/r_2)$.

Geometric core lemma.
The following lemma is the geometric core of our argument and the setup is shown in Figure <ref> (top left).
We use this lemma to conclude that if a set $Q$ of pieces cover most of $D_1$, then they have corners whose angles sum to a number close to $\beta$.
It then follows from the unique angle property that $Q$ consists of just one piece.

Let $W_1,\ldots,W_m$ be a collection of triangles each of which $W_i=x_iy_iz_i$ has one corner $y_i$ in $D_1$ and the segment $x_iz_i$ disjoint from $D$.
Let $\beta_i$ be the angle of $W_i$ at $y_i$ and suppose that $\beta_i\in [\alpha_{\min},\alpha_{\max}]$.
Suppose that $W_1,\ldots,W_m$ are pairwise interior disjoint and that the interior of each $W_j$ is disjoint from $\out{t_2}\out{y}$ and $\out{y}\out{s_2}$.
Let $\mathcal W\mydef\bigcup_{j=1}^m W_j$.