11institutetext:  IDLab, Department of Information Technology
Ghent University - imec
Ghent, Belgium
11email<EMAIL_ADDRESS>
# Disentangling What and Where for 3D Object-Centric Representations Through
Active Inference

Toon Van de Maele  Tim Verbelen  Ozan Çatal and Bart Dhoedt

###### Abstract

Although modern object detection and classification models achieve high
accuracy, these are typically constrained in advance on a fixed train set and
are therefore not flexible to deal with novel, unseen object categories.
Moreover, these models most often operate on a single frame, which may yield
incorrect classifications in case of ambiguous viewpoints. In this paper, we
propose an active inference agent that actively gathers evidence for object
classifications, and can learn novel object categories over time. Drawing
inspiration from the human brain, we build object-centric generative models
composed of two information streams, a what- and a where-stream. The what-
stream predicts whether the observed object belongs to a specific category,
while the where-stream is responsible for representing the object in its
internal 3D reference frame. We show that our agent (i) is able to learn
representations for many object categories in an unsupervised way, (ii)
achieves state-of-the-art classification accuracies, actively resolving
ambiguity when required and (iii) identifies novel object categories.
Furthermore, we validate our system in an end-to-end fashion where the agent
is able to search for an object at a given pose from a pixel-based rendering.
We believe that this is a first step towards building modular, intelligent
systems that can be used for a wide range of tasks involving three dimensional
objects.

###### Keywords:

Deep Learning, Object Recognition, Object Pose Estimation, Active Inference

##  1 Introduction

In the last decade, we have seen a proliferation of deep learning systems,
especially in the field of image classificaton [15, 10]. Although these
systems show high accuracies on various classification benchmarks, their
applicability is typically limited to a fixed input distribution based on the
dataset used during training. In contrast, the real world is not stationary,
which urges the need for continual learning [7]. Also, these classifiers lack
the concept of action, which renders them vulnerable to ambiguous and
adverserial samples [6]. As humans, we will typically move around and sample
more viewpoints to improve the precision of our classification, illustrating
the importance of embodiment in building intelligent agents [22].

Active inference offers a unified treatment of perception, action and
learning, which states that intelligent systems build a generative model of
their world and operate by minimizing a bound on surprise, i.e. the
variational free energy [5]. In [18], Parr et al. propose a model for (human)
vision, which considers a scene as a factorization of separate (parts of)
objects, encoding their identity, scale and pose. This is in line with the so
called two stream hypothesis, which states that visual information is
processed by a dorsal (“where”) stream on the one hand, representing where an
object is in the space, and a ventral (“what”) stream on the other hand,
representing object identity [4]. Similarly, Hawkins et al. propose that
cortical columns in the neocortex track objects and their pose in a local
reference frame, encoded by cortical grid cells [9].

In this paper, we propose a system that builds on these principles for
learning object-centric representations that allow for accurate
classification. Inspired by cortical columns, our system is composed of
separate deep neural networks, called Cortical Column Networks (CCN), where
each CCN learns a representation of a single type of 3D object in a local
reference frame. The ensemble of CCNs forms the agent’s generative model,
which is optimized by minimizing free energy. By also minimizing the expected
free energy in the future, we show that our agent can realize preferred
viewpoints for certain objects, while also being urged to resolve ambiguity on
object identiy.

We evaluate our agent on pixel data rendered from 3D objects from the YCB
benchmarking dataset [1], where the agent can control the viewpoint. We
compare the performance of an embodied and a static agent for classification,
and show that classification accuracy is higher for the embodied agent.
Additionally, we leverage the where stream for implicit pose estimation of the
objects.

##  2 Method

In active inference, an agent acts and learns in order to minimize an upper
bound on the negative log evidence of its observations, given its generative
model of the world i.e. the free energy. In this section, we first formally
introduce the generative model of our agent for representing 3D objects. Next
we discuss how we instantiate and train this generative model using deep
neural networks. Finally, we show how action selection is driven by minimizing
expected free energy in the future.

###  2.1 A generative model for object-centric perception

Our generative model is based on [18], but focused on representing a single
object. Concretely, our agent obtains pixel observations $\mathbf{o}_{0:t}$
that render a 3D object with identity $\mathbf{i}$ as viewed from certain
viewpoints $\mathbf{v}_{0:t}$ specified in an object-local reference frame.
Each time step $t$ the agent can perform an action $\mathbf{a}_{t}$, resulting
in a relative translation and rotation of the camera. The joint probability
distribution then factorizes as:

$p(\mathbf{o}_{0:t},\mathbf{a}_{0:t-1},\mathbf{v}_{0:t},\mathbf{i})=p(\mathbf{i})\prod_{t}p(\mathbf{o}_{t}|\mathbf{v}_{t},\mathbf{i})p(\mathbf{v}_{t}|\mathbf{v}_{t-1},\mathbf{a}_{t-1})p(\mathbf{a}_{t-1})$
(1)

Using the approximate posterior
$q(\mathbf{i},\mathbf{v}_{0:t}|\mathbf{o}_{0:t})=q(\mathbf{i}|\mathbf{o}_{0:t})\sum_{t}q(\mathbf{v}_{t}|\mathbf{i},\mathbf{o}_{t})$,
the free energy becomes:

$\begin{split}F&=\mathbb{E}_{q(\mathbf{i},\mathbf{v}_{0:t})}[\log
q(\mathbf{i},\mathbf{v}_{0:t}|\mathbf{o}_{0:t})-\log
p(\mathbf{o}_{0:t},\mathbf{a}_{0:t-1},\mathbf{v}_{0:t},\mathbf{i})]\\\
&\stackrel{{\scriptstyle+}}{{=}}D_{KL}[q(\mathbf{i}|\mathbf{o}_{0:t})||p(\mathbf{i})]+\sum_{t}D_{KL}[q(\mathbf{v}_{t}|\mathbf{i},\mathbf{o}_{t})||p(\mathbf{v}_{t}|\mathbf{v}_{t-1},\mathbf{a}_{t-1})]\\\
&\;\;\;\;-\mathbb{E}_{q(\mathbf{i},\mathbf{v}_{0:t})}[\log
p(\mathbf{o}_{t}|\mathbf{v}_{t},\mathbf{i})]\end{split}$ (2)

This shows that minimizing free energy is equivalent to maximizing the
accuracy, i.e. predicting the observation for a given object identity and
viewpoint, while minimizing complexity of the posterior models.

###  2.2 An ensemble of CCNs

We instantiate the generative model using deep neural networks similar to a
variational autoencoder (VAE) [14, 19] with an encoder and decoder part. For
each object identity, we train a separate encoder-decoder pair, since
$p(\mathbf{o}_{t}|\mathbf{v}_{t},\mathbf{i})=\sum_{k}p(\mathbf{o}_{t}|\mathbf{v}_{t},i=k)$.
Similarly the encoder outputs distribution parameters for the object identity
$q(i=k|\mathbf{o}_{t})$ and viewpoint $q(\mathbf{v}_{t}|\mathbf{o}_{t},i=k)$,
the former parameterized as a Bernoulli variable, the latter as a multivariate
Gaussian with a diagonal covariance matrix. Finally, we also parameterize the
transition model $p(\mathbf{v}_{t}|\mathbf{v}_{t-1},\mathbf{a}_{t-1},i=k)$
which enforces $\mathbf{v}$ to encode relative viewpoint information.

Intuitively, each encoder-decoder pair captures the information about a single
object class, with a “what” stream modeled as a binary classifier of whether
an observation belongs to a certain object identiy, and a “where” stream
encoding the observer viewpoint w.r.t. a local, object-specific reference
frame. We call such a pair a Cortical Column Network (CCN), as it mimicks the
“voting for object at pose” behavior of cortical columns in the neocortex as
hypothesized in [9]. This is illustrated in Figure 1. The agent hence entails
a generative model as an ensemble of CCNs. We obtain
$q(\mathbf{i}|\mathbf{o}_{0:t})\propto
q(\mathbf{i}|\mathbf{o}_{0:t-1})q(\mathbf{i}|\mathbf{o}_{t})$, where
$q(\mathbf{i}|\mathbf{o}_{t})$ is a Categorical distribution from the CCN
votes $q(i=k|\mathbf{o}_{t})$, and $q(\mathbf{i}|\mathbf{o}_{0:t-1})$ is a
conjugate prior Dirichlet distribution whose concencentration parameters are
aggregated votes from previous observations, as updated in a Bayesian filter
[25]. This process computes the posterior belief over the different timesteps.
The Dirichlet distribution reflects the prior that an object is unlikely to
change its category between timesteps. We also include an “other” object
class, which is activate when none of the object classes receive votes, hence
enabling the agent to detect novel object categories.

Figure 1: A single CCN. Observation $\mathbf{o}_{t}$ is processed by an
encoder and provides a belief over the object identity $p(i=k|\mathbf{o}_{t})$
and over the observers pose $p(\mathbf{v}_{t}|i=k,\mathbf{o}_{t})$. From this
distribution, a sample $\mathbf{\hat{v}}_{t}$ is drawn and is decoded in a
reconstructed observation $\mathbf{\hat{o}}_{t}$. This sample is also
transformed together with an action $\mathbf{a}_{t}$ into a belief over a
future pose $\mathbf{v}_{t+1}$.

Each CCN is trained in an end-to-end fashion using a dataset of object
observation pairs and the relative camera transform between them for each
object class. To minimize Equation 2, we use MSE loss on the reconstructions
and a KL divergence between the viewpoint posterior and transition model. The
identity posterior is trained as a binary classifier, sampling positive and
negative anchors from the dataset. For more details on the training loss and
model architectures, the reader is referred to the appendix.

###  2.3 Classification by minimizing expected free energy

Crucially in active inference, an agent will select the action that minimizes
the expected free energy in the future $G$. In our case, this yields:

$\begin{split}G(\mathbf{a}_{t})&=\mathbb{E}_{q(\mathbf{i},\mathbf{v}_{0:t+1},\mathbf{o}_{t+1})}[\log
q(\mathbf{i},\mathbf{v}_{0:t+1}|\mathbf{o}_{0:t},\mathbf{a}_{t})-\log
p(\mathbf{o}_{0:t+1},\mathbf{a}_{0:t-1},\mathbf{v}_{0:t+1},\mathbf{i}|\mathbf{a}_{t})]\\\
&\approx\mathbb{E}_{q(\mathbf{o}_{t+1})}[-\log p(\mathbf{o}_{0:t+1})]\\\
&\;\;\;\;-\mathbb{E}_{q(\mathbf{i},\mathbf{v}_{0:t+1},\mathbf{o}_{t+1})}[\log
q(\mathbf{i}|\mathbf{o}_{0:t+1},\mathbf{a}_{t})-\log
q(\mathbf{i}|\mathbf{o}_{0:t},\mathbf{a}_{t})]\\\
&\;\;\;\;-\mathbb{E}_{q(\mathbf{i},\mathbf{v}_{0:t+1},\mathbf{o}_{t+1})}[\log
q(\mathbf{v}_{0:t+1}|\mathbf{i},\mathbf{o}_{0:t+1},\mathbf{a}_{t})-\log
q(\mathbf{v}_{0:t+1}|\mathbf{i},\mathbf{o}_{0:t},\mathbf{a}_{t})]\end{split}$
(3)

The expected free energy unpacks into three terms, the first is an
instrumental term that indicates that the agent is driven to some prior
preferred observations, whereas the second and third term encode the expected
information gain for the object identity and the object pose for a certain
action. This shows how the agent can be steered to seeing a certain object at
a certain pose, which could be for example a grasp position in the case of a
robotic manipulator. On the other hand, in the absence of preferences, the
agent will query new viewpoints that provide information on the object
identity and pose, effectively trying to get a better classification.

##  3 Experiments

We evaluate our model for an agent in a 3D environment, where 3D models of
objects from the YCB dataset [1] are rendered from a certain camera viewpoint.
The agent actions are then defined as relative transforms (i.e. rotation and
translation), moving the camera viewpoint. This setup closely mimicks a robot
manipulator with an in-hand camera, but without kinematic constraints [26].

We create a dataset using 3D meshes of objects from the YCB dataset [1]. For
each of 9 “known” objects, 14000 viewpoints and their corresponding view, for
which the object is centered in view, are generated as a train set. During
training, pairs of two views are randomly selected, for which the action is
defined as the relative transform between these two viewpoints.

We first validate that the CCN ensemble is able to learn pose and identity
representations unsupervisedly by minimizing free energy. Next, we show how
the expected free energy allows to agent to infer actions that can bring the
agent to a preferred pose relative to an object on the one hand, and resolve
ambiguity for inferring an object identity on the other hand.

(a)

(b)

Figure 2: (a) The ROC curve for individual CCNs. Negative samples are
observations from the test set: padlock, power drill, knife, orange and tuna
fish can. (b) The ground truth (top row), the reconstruction (second row), and
imagined transformed observations (other rows) are shown for multiple YCB
objects [1].

###  3.1 The “what” stream: object recognition

First, we evaluate the performance of each individual CCN “what” binary
classifier. The ROC curves are shown in Figure 2(a) where each CCN is tested
on a dataset with 3000 novel views for each of the 9 known objects, and 3000
views from 5 objects, it has never seen during training. For all objects we
achieve near-perfect ROC curves, which can be attributed to the fact that each
CCN can focus on particular features that distinguish a particular object from
the others. Investigating the impact on the ROC performance when using real-
world observations instead of 3D renders of predefined object models would be
an interesting avenue for future work.

###  3.2 The “where” stream: implicit pose estimation

Crucially, our CCNs not only learn a classification output, but also an
implicit representation of the 3D structure of the object at hand. As
discussed in Section 2, this is encoded in a latent code $\mathbf{v}_{t}$,
from which the model can reconstruct the given viewpoint using the decoder, or
imagine other viewpoints after a relative transform using the transition
model. This is illustrated in Figure 2(b), where the first row shows ground
truth object observations, the second row shows the reconstruction after
encoding, and the third and fourth row show imagined other viewpoints.

We can now use the CCN to infer the actions that will yield some “preferred”
observation, by minimizing the expected free energy in Equation 3. This is
useful for example to instruct a robotic manipulator to a certain grasp point
for an object. As computing $G$ for every action is intractable, we sample
1000 random relative transforms for which $G$ is calculated. A transform is
sampled by first sampling a target viewpoint in 3D space uniformly in the
workspace. The orientation is then determined so that the camera looks at the
center of gravity of the object. The relative transform can then be computed
between both current and target sampled poses. The identity transform is
always provided as an option, allowing the agent to stay at its current pose
when no better option is found. This results in the agent finding the
estimated pose. Figure 3 shows qualitative trajectories for estimating the
correct pose from both a mug and a pudding box. On average, the pose
estimation process converges after 3 steps, and the resulting final pose lies
around 1 mm (average of 1.4 mm) and 5 degrees (average of 4.7 degree) in
distance and angle compared to the ground truth. We provide a more detailed
table in Appendix B.

Figure 3: The agent is provided with a preferred observation (first column
left), and an intial observation (second column). The agent infers the
relative transforms to reach the preferred observation.

###  3.3 Embodied agents for improved classification

Whereas previously we evaluated the binary classfication performance of
individual CCNs, we now evaluate the performance of the CCN ensemble as an
$n+1$-way classifier, with $n$ object classes and one “other” class.

We evaluate an embodied agent that can query extra viewpoints to improve its
classification. In this case, the agent again infers actions that minimize the
expected free energy G, effectively maximizing information gain on the object
identity. In this case, CCN votes are aggregated in the concentration
parameters of a Dirichlet distribution, as described in Section 2. We also add
a fixed $0.5$ value vote for the “other” object category which accounts for
evindence for the “other” class when none of the CCNs “fire”. We compare this
agent with a static agent that only has a single view. In this case, only a
single vote is used for the parameters of the Dirichlet distribution.

To evaluate the performance, we randomly sample 20 views for each of 14 object
classes (9 known object classes and 5 never seen before), and evaluate both
the static and embodied classificaton accuracy. The results are shown in
Figure 4(a). Whereas the static agent achieves an overall accuracy of 92.5%,
the embodied agent consistently improves in accuracy, reaching 98%, as more
viewpoints are queried, in line with [8]. The error bounds are computed over 5
different random seeds and represent the 95% HDI. Figure 4(b) shows the
imagined observations for the largest and smallest expected free energy $G$.
Figure 4(b) shows imagined views with highest or lowest $G$, and illustrates
that the active inference agent prefers observations where the object is
clearly in view from a more close up view, rather than more ambiguous
viewpoints.

(a)

(b)

Figure 4: (a) Performance of the CCN ensemble in a static (red) and an
embodied agent, driven through active inference (blue). The agent is provided
with 20 situations for each of the 9 known objects and 5 never-before seen
test objects. (b) Imagined views for actions that result in the largest and
smallest expected free energy $G$.

##  4 Related work

Deep learning has been widely used for static image classification [15, 10].
However, recent work also focused on active vision. In [26] a generative model
learning representations of a whole 3D scene was used for an active inference
agent, whereas in [2] an explicit what and where stream were modeled for
classifying MNIST digits.

Recently a lot of progress has been made in methods that learn the 3D geometry
of objects. The geometry can either be learned implicitly using Neural
Radiance Fields (NeRF) [16] or Generative Query Networks (GQN) [3] or
explicitly using Scene Representation Networks (SNR) [24]. However these
approaches either have to generalize to a large variety of objects, which
results in an involved training process requiring a lot of data, or they
optimize for a single observation, limiting the flexibility.

Continual learning methods are able to use experience gathered during
deployment of a system to improve the system over time. Typical approaches
involve an ensemble of classifiers, that operate on a subset of the inputs,
either by splitting the train data in specific subsets to train a mixture of
experts [12], or by identifying clusters in a shared latent space and training
separate classifiers for separate clusters [23].

The use of information gain has also been used as an exploration strategy
outside of the active inference community, in which it substantially improves
exploratory performance on a number of Atari tasks [17].

While most approaches tackle these problems separately, we propose a
biologically inspired method that learns object-centric representations in an
unsupervised manner for both the object identity and its geometric properties.

##  5 Discussion

We believe that this is a first step towards manipulation of three dimensional
objects, and plan to extend this work to a real-world robot setup. In this
case, the robotic agent needs to make inferences on the object pose and
identity that is present in the workspace. In case the object is identified,
the agent is attracted to preferred observations, e.g. for grasping or
manipulating the object. In case a different, novel object class is
identified, a new CCN is instantiated and trained on these novel object views.
In this case, we could infer the viewpoints that have a high information gain
on model parameters in an active learning setting, which can also be written
as an expected free energy term [5]. We can further extend the generative
model to also take into account multiple objects in the scene and modelling
inter-object relations and geometry.

A limitation of our current setup is that it can only deal with a single
object in the center of the view. As multi-object scenes are ubiquitous in the
real world, this is a natural direction for future work. We propose a solution
in which the agent can divide its spatial attention on the observations by
looking at the CCN activations at different patches on the observation. Once
an object and its relative reference frame is found, these can be linked using
a global, ego-centric reference frame of the agent [18]. This way, a
hierarchical generative model of the whole workspace, composed of different
object is constructed. These latent parameters can then be propagated over
time through a predictive model, and can in that way deal with occlusions.

In principle, one could instantiate a hierarchy of CCNs, where higher level
CCNs process the output of lower level CCNs, effectively modeling part-whole
relationships. This is similar to Capsule Networks [21] and GLOM [11], and
corresponds better with the 1000 brains theory [9]. However, given the limited
scalability of state of the art implementations of such hierarchical
approaches [21], we adopted CCNs that operate on the level that is most
important for a robot operating in a workspace, i.e. the discrete object
level.

We found that failure cases exist when CCNs incorrectly “fire” for unseen
objects. This confusion occurs for some objects yielding a non-perfect
classification score. We could further improve the system by also taking into
account how good novel observations match our predictions in the past.

##  6 Conclusion

In this paper we showed a novel approach to modelling 3D object properties,
drawing inspiration from current development in the Neuroscientific domain. We
proposed to model a separate what- and where stream for each individual object
and are able to use these models for object identification as well as implicit
object pose estimation. We show that through embodiment, these models can
aggregate information and increase classification performance. Additionally,
we show that by following the free energy formulation, these module networks
can be used for implicit pose estimation of the objects.

#### Acknowledgments

This research received funding from the Flemish Government (AI Research
Program). Ozan Çatal was funded by a Ph.D. grant of the Flanders Research
Foundation (FWO). Part of this work has been supported by Flanders Innovation
& Entrepreneurship, by way of grant agreement HBC.2020.2347.

## References

  * [1] Berk Calli, Arjun Singh, Aaron Walsman, Siddhartha Srinivasa, Pieter Abbeel, and Aaron M. Dollar.  The ycb object and model set: Towards common benchmarks for manipulation research.  In 2015 International Conference on Advanced Robotics (ICAR), pages 510–517, 2015.
  * [2] Emmanuel Daucé and Laurent U Perrinet.  Visual search as active inference.  In IWAI 2020, 2020.
  * [3] S. M. Ali Eslami, Danilo Jimenez Rezende, Frederic Besse, Fabio Viola, Ari S. Morcos, Marta Garnelo, Avraham Ruderman, Andrei A. Rusu, Ivo Danihelka, Karol Gregor, David P. Reichert, Lars Buesing, Theophane Weber, Oriol Vinyals, Dan Rosenbaum, Neil Rabinowitz, Helen King, Chloe Hillier, Matt Botvinick, Daan Wierstra, Koray Kavukcuoglu, and Demis Hassabis.  Neural scene representation and rendering.  Science, 360(6394):1204–1210, June 2018.
  * [4] George Ettlinger.  “object vision” and “spatial vision”: The neuropsychological evidence for the distinction.  Cortex, 26(3):319–341, 1990.
  * [5] Karl Friston, Thomas FitzGerald, Francesco Rigoli, Philipp Schwartenbeck, John O’Doherty, and Giovanni Pezzulo.  Active inference and learning.  Neuroscience & Biobehavioral Reviews, 68:862–879, 2016.
  * [6] Justin Gilmer, Ryan P. Adams, Ian J. Goodfellow, David G. Andersen, and George E. Dahl.  Motivating the rules of the game for adversarial example research.  CoRR, abs/1807.06732, 2018.
  * [7] Raia Hadsell, Dushyant Rao, Andrei A. Rusu, and Razvan Pascanu.  Embracing change: Continual learning in deep neural networks.  Trends in Cognitive Sciences, 24(12):1028–1040, December 2020.
  * [8] Jeff Hawkins, Subutai Ahmad, and Yuwei Cui.  A theory of how columns in the neocortex enable learning the structure of the world.  Frontiers in Neural Circuits, 11:81, 2017.
  * [9] Jeff Hawkins, Marcus Lewis, Mirko Klukas, Scott Purdy, and Subutai Ahmad.  A framework for intelligence and cortical function based on grid cells in the neocortex.  Frontiers in Neural Circuits, 12:121, 2019.
  * [10] Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun.  Deep residual learning for image recognition.  In 2016 IEEE Conference on Computer Vision and Pattern Recognition (CVPR), pages 770–778, June 2016.
  * [11] Geoffrey E. Hinton.  How to represent part-whole hierarchies in a neural network.  CoRR, abs/2102.12627, 2021.
  * [12] Robert A. Jacobs, Michael I. Jordan, Steven J. Nowlan, and Geoffrey E. Hinton.  Adaptive mixtures of local experts.  Neural Computation, 3(1):79–87, 1991.
  * [13] Diederik P. Kingma and Jimmy Ba.  Adam: A method for stochastic optimization, 2017.
  * [14] Diederik P Kingma and Max Welling.  Auto-encoding variational bayes.  arXiv preprint arXiv:1312.6114, 2013.
  * [15] Alex Krizhevsky, Ilya Sutskever, and Geoffrey E. Hinton.  Imagenet classification with deep convolutional neural networks.  In Proceedings of the 25th International Conference on Neural Information Processing Systems - Volume 1, NIPS’12, page 1097–1105, Red Hook, NY, USA, 2012. Curran Associates Inc.
  * [16] Ben Mildenhall, Pratul P Srinivasan, Matthew Tancik, Jonathan T Barron, Ravi Ramamoorthi, and Ren Ng.  Nerf: Representing scenes as neural radiance fields for view synthesis.  In European Conference on Computer Vision, pages 405–421. Springer, 2020.
  * [17] Nikolay Nikolov, Johannes Kirschner, Felix Berkenkamp, and Andreas Krause.  Information-directed exploration for deep reinforcement learning, 2019\.
  * [18] Thomas Parr, Noor Sajid, Lancelot Da Costa, M. Berk Mirza, and Karl J. Friston.  Generative models for active vision.  Frontiers in Neurorobotics, 15:34, 2021.
  * [19] Danilo Jimenez Rezende, Shakir Mohamed, and Daan Wierstra.  Stochastic backpropagation and approximate inference in deep generative models, 2014.
  * [20] Danilo Jimenez Rezende and Fabio Viola.  Taming vaes, 2018.
  * [21] Sara Sabour, Nicholas Frosst, and Geoffrey E. Hinton.  Dynamic routing between capsules.  CoRR, abs/1710.09829, 2017.
  * [22] Adam Safron.  The radically embodied conscious cybernetic bayesian brain: From free energy to free will and back again.  Entropy, 23(6), 2021.
  * [23] Murray Shanahan, Christos Kaplanis, and Jovana Mitrovic.  Encoders and ensembles for task-free continual learning.  CoRR, abs/2105.13327, 2021.
  * [24] Vincent Sitzmann, Michael Zollhöfer, and Gordon Wetzstein.  Scene representation networks: Continuous 3d-structure-aware neural scene representations.  In Advances in Neural Information Processing Systems, 2019.
  * [25] Ryan Smith, Karl Friston, and Christopher Whyte.  A step-by-step tutorial on active inference and its application to empirical data, Jan 2021.
  * [26] Toon Van de Maele, Tim Verbelen, Ozan Çatal, Cedric De Boom, and Bart Dhoedt.  Frontiers in Neurorobotics, 15:14, 2021.

##  Appendix A Neural Network Architecture and Training Details

The neural network is based on a variational autoencoder [14, 19] consisting
of an encoder and a decoder. The encoder $\phi_{\theta}$ uses a convolutional
pipeline to map a high dimensional input image (64x64x3) into a low
dimensional latent distribution. We parameterize this distribution as a
Bernouilli distribution representing the identity of the object and the camera
viewpoint as a Multivariate Normal distribution with diagonal covariance
matrix of 8 latent dimensions. The decoder $\psi_{\theta}$ then takes a sample
from the viewpoint and is able to reconstruct the observation through a
convolutional pipeline using transposed convolutions. In addition to a
traditional variational autoencoder, we have a transition model
$\chi_{\theta}$ that transforms a sample from the viewpoint distribution to a
novel latent distribution, provided with an action. This action is a 7D vector
representing the translation as coordinates in and rotation in quaternion
representation. The model architecture for encoder, decoder and transition
models are shown in Table 1, Table 2 and Table 3, respectively.

The model is optimized end-to-end through the minimization of Free Energy as
described in Equation 2. The expectations over the different terms are
approximated through stochastic gradient descent using the Adam optimizer
[13]. As minimization of negative log likelihood over reconstruction is
equivalent to minimization of the Mean Squared Error, this is used in
practice. Similarly, the negative log likelihood over the identity is
implemented as a binary cross-entropy term. We choose the prior belief over
$\mathbf{v}$ to be an isotropic Gaussian with variance 1. The individual terms
of the loss function are constrained and weighted using Lagrangian multipliers
[20]. We consider only a single timestep during the optimization process. In
practice this boils down to:

$\begin{split}L_{FE}=&\lambda_{1}\cdot L_{BCE}(\hat{i},i)+\lambda_{2}\cdot
L_{MSE}(\psi_{\theta}(\mathbf{\hat{v}}_{t+1}),\mathbf{o}_{t+1})\\\
&+D_{KL}[\underbrace{\chi_{\theta}(\mathbf{v}_{t},\mathbf{a}_{t})}_{q(\mathbf{v}_{t+1}|\mathbf{v}_{t},\mathbf{a}_{t},\mathbf{i})}||\underbrace{\phi_{\theta}(\mathbf{\hat{o}})}_{p(\mathbf{v}_{t+1}|\mathbf{i},\mathbf{o}_{t})}]\end{split}$
(4)

where $\hat{i}$ is the prediction $\phi_{\theta}(\mathbf{o}_{t})$ of the what-
stream for the encoder, $\mathbf{\hat{v}_{t+1}}$ is a sample from the
predicted transitioned distribution
$\chi_{\theta}(\mathbf{v}_{t},\mathbf{a}_{t})$ and $\mathbf{\hat{o}}_{t+1}$ is
the expected observation from viewpoint $\mathbf{\hat{v}_{t+1}}$, decoded
through $\psi_{\theta}(\mathbf{v}_{t+1})$. The $\lambda_{i}$ variables
represent the Lagrangian multipliers used in the optimization process.

During training, pairs of observations $\mathbf{o}_{t}$ and $\mathbf{o}_{t+1}$
and corresponding action $\mathbf{a}_{t}$ are required. To maximize data
efficiency, the equation is also evaluated for zero-actions using only a
single observation, and reconstructing this directly without transition model.

Table 1: Neural network architecture for the image encoder. All strides are applied with a factor 2. The input image has a shape of 3x64x64. The output of the convolutional pipeline is used for three different heads. The first predicts the mean of the distribution $\mu$, the second head predicts the natural logarithm of the variance $\sigma^{2}$, for stability reasons and finally the third head predicts the classification output score $c$ as a value between zero and one after activation through the sigmoid activation function. Output label | Layer | Kernel size | # Filters
---|---|---|---
| Strided Conv2D | 4 | 8
| LeakyReLU |  |
| Strided Conv2D | 4 | 16
| LeakyReLU |  |
| Strided Conv 2D | 4 | 32
| LeakyReLU |  |
| Strided Conv2D | 4 | 64
| LeakyReLU |  |
$h$ | Reshape to 128 |  |
$\mu$ | Linear (input: $h$) |  | 8
ln $\sigma^{2}$ | Linear (input: $h$) |  | 8
$c$ | Linear + Sigmoid (input: $h$) |  | 1
Table 2: Neural network architecture for the image decoder. The input of this model is a sample drawn from the latent distribution, either straight from the encoder, or transitioned through the transition model. All transpose layers use a stride of two. The final layer of the model is a regular convolution with stride 1 and kernel size 1, after which a sigmoid activation is applied to map the outputs in the correct image range. Layer | Kernel size | # Filters
---|---|---
Linear |  | 128
Reshape to 128x1x1 |  |
ConvTranspose2D | 5 | 64
LeakyReLU |  |
ConvTranspose2D | 5 | 64
LeakyReLU |  |
ConvTranspose2D | 6 | 32
LeakyReLU |  |
ConvTranspose2D | 6 | 16
LeakyReLU |  |
Conv2D | 1 | 3
Sigmoid |  |
Table 3: Neural network architecture for the transition model. The input from this model is an 8 dimensional latent code, concatenated with the 7-dimensional representation of the relative transform (position coordinates and orientation in quaternion representation). For stability reasons, the log-variance is predicted rather than the variance directly. Output label | Layer | # Filters
---|---|---
| Linear | 128
| LeakyReLU |
| Linear | 256
| LeakyReLU |
| Linear | 256
| LeakyReLU |
$\mu$ | Linear | 8
ln $\sigma^{2}$ | Linear | 8

##  Appendix B Additional experimental details

In Table 4, the computed angular and translational distances for the 9
evaluated objects are shown. Figure 5 shows a sequence of imaginations for all
9 objects, the top row represents the ground truth input, the second row the
reconstruction and the subsequent rows are imagined observations along a
trajectory.

Table 4: The mean distance error in meters and angle error in radians for different objects of the YCB dataset [1] in our simulated environment. For each object 20 arbitrary target poses were generated over which the mean values are computed.  Object | Distance error (m) | Angle error (rad)
---|---|---
chips can | 0.00328 $\pm$ 0.00824 | 0.15997 $\pm$ 0.21259
master chef can | 0.00036 $\pm$ 0.00034 | 0.06246 $\pm$ 0.03844
cracker box | 0.00028 $\pm$ 0.00023 | 0.04659 $\pm$ 0.02674
tomato soup can | 0.00073 $\pm$ 0.00104 | 0.08653 $\pm$ 0.07021
mustard bottle | 0.00070 $\pm$ 0.00072 | 0.06351 $\pm$ 0.03818
mug | 0.00083 $\pm$ 0.00128 | 0.09098 $\pm$ 0.10232
pudding box | 0.00051 $\pm$ 0.00052 | 0.06190 $\pm$ 0.03843
banana | 0.00055 $\pm$ 0.00042 | 0.07482 $\pm$ 0.03592
strawberry | 0.00573 $\pm$ 0.01181 | 0.16699 $\pm$ 0.15705

Figure 5: The top row represents the ground truth observation that was
provided as input to the model. The second row shows a direct reconstruction
when no action is applied to the transition model. All subsequent rows show
imagined observations along a trajectory.


# Efficient Segment Folding is Hard††thanks: This work was started during the
FWF–JSPS Japan–Austria Bilateral Seminar “Computational Geometry Seminar with
Applications to Sensor Networks” held in Zao (Japan) in 2018. The authors want
to thank all participants for the fruitful discussions. We want to thank the
anonymous reviewers for the insightful comments.

Takashi Horiyama Email<EMAIL_ADDRESS>Faculty of Information
Science and Technology, Hokkaido University, Sapporo, Japan  Fabian Klute
Email<EMAIL_ADDRESS>Supported by the Netherlands Organisation for
Scientific Research (NWO) under project no. 612.001.651 and by the Austrian
Science Fund (FWF): J-4510. Utrecht University, Utrecht, The Netherlands
Matias Korman Email<EMAIL_ADDRESS>Siemens EDA (formerly
Mentor Graphics), OR, USA  Irene Parada Email<EMAIL_ADDRESS>Research
partially supported by the Austrian Science Fund (FWF): W1230 and by
Independent Research Fund Denmark grant 2020-2023 (9131-00044B) “Dynamic
Network Analysis”. Technical University of Denmark, Lyngby, Denmark  Ryuhei
Uehara Email<EMAIL_ADDRESS>Supported by MEXT Kakenhi No. 17H06287 and
18H04091. School of Information Science, JAIST, Ishikawa, Japan  Katsuhisa
Yamanaka Email<EMAIL_ADDRESS>Faculty of Science and Engineering,
Iwate University, Iwate, Japan

###### Abstract

We introduce a computational origami problem which we call the segment folding
problem: given a set of $n$ line-segments in the plane the aim is to make
creases along all segments in the minimum number of folding steps. Note that a
folding might alter the relative position between the segments, and a segment
could split into two. We show that it is NP-hard to determine whether $n$ line
segments can be folded in $n$ simple folding operations.

##  1 Introduction

Origami designers around the world struggle with the problem of finding a
better way to fold an origami model. Recent advanced origami models require
substantial _precreasing_ of a prescribed mountain-valley pattern (getting
each crease folded slightly in the correct direction), and then folding all
the creases at once. For example, for folding the MIT seal _Mens et Manus_ in
“three easy steps”, Chan [4] spent roughly three hours precreasing, three
hours folding those creases, and four hours of artistic folding. The
precreasing component is particularly tedious. Thus, we wonder if this process
can be automated by folding robots. As of the writing of this paper, the most
recent robots for folding paper can achieve only quite simple foldings (see,
e.g., [3]), but we consider a future setting in which more difficult ones are
possible. In such a setting, we have a series of portions of the sheet that
need to be folded in some specified locations, and we would like to do it as
fast as possible (that is, in the minimum possible number of foldings).

We consider one of the simplest folding operations possible called _all-layers
simple fold_. An all-layers simple fold starts with a sheet in a flat folded
state and consists of the following three steps: (1) choose a crease line, (2)
fold all paper layers along this line, and (3) crease to make all paper layers
flat again.

In our model we start with a plain sheet of paper with no folds or creases
(say, a unit square). From that sheet we do all-layers simple folds one at a
time until we have reached our desired shape. We note that this is one of the
simplest folding models, and that many variants have been considered in the
literature (see [1] for other folding models).

This situation leads us to the following natural _segment folding problem_ :

Segment Folding Problem Input: A set $S$ of line segments
$s_{1},s_{2},\ldots,s_{|S|}$ in the plane (on a sheet of paper) and an integer
$\kappa$. Operation: Reflection (all-layers simple fold) along a line
containing one or more (parts of) segments $s_{i}$ for some
$i\in\\{1,\dots,|S|\\}$. Question: Is there a sequence of $\kappa$ operations
such that all (parts of) segments $s_{i}$ become reflection (crease) lines?

We remark that only folds along the supporting lines of the line segments are
possible. As we will see, this setting gives rise to interesting questions.
Notice that, when we fold along a line $\ell$, the location of all segments in
one side of the line are reflected (via line symmetry) onto the other half-
plane. In particular, if $\ell$ intersects the interior of some segment
$s_{j}$ for $j\leq n$, it may create two segments that form a $V$ shape and
meet at the folded line (it will create two segments if and only if $\ell$ and
$s_{j}$ do not meet at a right angle and $s_{j}\not\subset\ell$). Whenever
this happens, we have to fold the two subsegments since the original segment
has been split into two.

Figure 1: A problem instance that can be folded arbitrarily many times along
non-folded input segments. If you fold along the dashed lines, the instance
cycles through the four patterns and never ends. Note that in all cases we
have two segments forming a V shape and three almost but not exactly
orthogonal segments. Each folding changes the length and the position of the V
shape, but the overall structure remains the same. Note that it is possible to
fold this instance with a finite number of moves (folding any of the segments
that is not part of the V shape).

Because folding along a line may increase the number of folds that are needed,
we wonder if every instance can be folded with a finite number of fold
operations111We thank Takeshi Tokuyama for posing this question.. We say that
an instance is foldable if it has a solution to the segment folding problem in
a finite number of moves. To date, we do not know if every problem instance is
foldable; in Figure 1 we show an example admitting an infinite sequence of
folds. Another natural question is related to efficiency: If an instance is
foldable, can we find the sequence of folds? Ideally, one that minimizes that
number of fold operations that are needed? In this paper we prove that, unless
P=NP, we cannot find this optimal sequence in polynomial time.

######  Theorem 1.

Deciding whether a segment folding problem instance $S$ consisting of a set of
$|S|$ segments can be solved with $|S|$ folds is NP-hard.

##  2 Preliminaries

Let $S$ be a given set of $|S|$ segments in $\mathbb{R}^{2}$. Let $\ell_{s}$
be the supporting line of a segment $s\in S$ and let $R_{s}$ be the right open
half-plane222For a horizontal supporting line $\ell_{s}$ we can define $R_{s}$
to be the top half-plane. Else, the right open half-plane is the one that
contains all points $(\chi,0)$ for all values of $\chi$ larger than some
threshold value.  bounded by $\ell_{s}$. For a set $U\subseteq\mathbb{R}^{2}$
(in this paper $U$ is a collection of segments) and a segment $s\in S$, we
denote as $\mathcal{R}_{s}(U)$ the reflection of set $U$ along the supporting
line $\ell_{s}$ of segment $s$. A fold along the supporting line $\ell_{s}$ of
a segment $s\in S$ creates a new set of segments
$S^{\prime}:=\operatorname{cl}(\\{(S\cap
R_{s})\cup\mathcal{R}(S\setminus\operatorname{cl}(R_{s}))\\})$ where the
segments (or parts of them) from $S$ in the left half-plane defined by
$\ell_{s}$ are reflected into the right half-plane (or viceversa). We denote
that operation a _fold along $s$_, or simply, _folding $s$_. Note that we only
allow folding along segments of $S$.

We start by making straight-forward observations about basic folds. Recall
that we are interested in deciding whether an instance can be folded using at
most $|S|$ folds. Folding along a segment $s$ on the convex hull does not
change the relative positions of the remaining segments, and therefore the
resulting instance after folding is the same or a reflected copy of the one
resulting from just removing $s$. These two instances are equivalent for the
problem we consider and therefore it is enough to just remove $s$:

######  Observation 2.

If a segment $s$ lies on the boundary of the convex hull of our set of
segments, a fold along it does not change any of the remaining segments.

When a folding line supporting a segment $s\in S$ intersects the interior of
another segment $s^{\prime}\in S$ in a non-right angle, this second segment is
split into two segments that share an endpoint. Both segments are now part of
$S$ and they must therefore become reflection lines. Let $S$ be a set of
segments in $\mathbb{R}^{2}$, we say a segment $s\in S$ _stabs_ $t\in S$,
$s\neq t$, if the supporting line $l_{s}$ intersects $t$, but $s$ and $t$ do
not share a common point. We say a segment $s\in S$ is stabbing, if there
exists a $t\in S$ such that $s$ stabs $t$.

######  Observation 3.

Let $S$ be a set of segments in $\mathbb{R}^{2}$ and $s\in S$ be a non-
stabbing segment, then if a fold along $s$ does not produce a crossing between
another two segments, no segment is split.

Consider an instance in general position, that is, no two segments of $S$ lie
on the same line even after we have performed up to $|S|$ folds. In that case
each of the first $|S|$ folds can only decrease the size of $S$ by one.

######  Observation 4.

Given a segment folding problem instance $S$ in general position, a solution
sequence of length $|S|$ cannot make a fold along a stabbing segment nor a
fold that makes two segments cross in a non-right angle.

This claim follows from $(i)$ the fact that, in general position, folding
along a stabbing segment does not decrease the number of segments; $(ii)$ two
segments crossing in a non-right angle cannot be folded in less than $3$
folds, and $(iii)$ we are interested in determining if a problem instance $S$
can be solved with at most $|S|$ folds.

##  3 Reduction

The reduction we first describe in this section uses for simplicity two
perpendicular directions for the segments, and thus, constructs a set of
segments $S$ that is not in general position. In the folding sequence we
disallow folding along stabbing segments and along segments that produce
crossings. More precisely, the problem we first show hardness for is the
_restricted segment folding problem_ :

Restricted Segment Folding Problem Input: A set $S$ of line segments
$s_{1},s_{2},\ldots,s_{|S|}$ in the plane and an integer $\kappa$. Operation:
Fold along a line $\ell$ containing one or more segments $s_{i}$ for some
$i\in\\{1,\dots,|S|\\}$. The line $\ell$ must not intersect the interior of
any other segment in $S$ and folding along it must not produce crossings
between segments in $S$. Question: Is there a sequence of $\kappa$ operations
such that all (parts of) segments $s_{i}$ become folding lines?

We show the following result:

######  Theorem 5.

Deciding whether a restricted segment folding problem instance $S$ consisting
of a set of $|S|$ segments can be solved with $|S|$ folds is strongly NP-hard,
even if the segments in $S$ have only three directions.

In Section 3.7 we show how to modify the construction in the reduction in the
proof of Theorem 5 to show NP-hardness for the segment folding problem
(proving Theorem 1).

We will prove Theorems 1 and 5 by reducing from 3SAT. A 3SAT formula is given
by a set $\\{x_{1},\dots,x_{n}\\}$ of boolean variables and
$\\{c_{1},\dots,c_{m}\\}$ of clauses. Each clause contains the disjunction of
three literals. A literal is a positive or negative occurrence of a variable.
A formula $F(x_{1},\dots,x_{n})$ is the conjunction of the clauses
$c_{1},\dots,c_{m}$. In 3SAT we say $F$ is satisfied if and only if for each
clause $c_{j}$ at least one of its literals evaluates to true. For the
reduction we will construct a set $S$ of segments from a given 3SAT formula
$F$. To make the final correctness proof simpler, we consider only 3SAT
formulas in which no clause has only positive or negative literals.
Transforming a given 3SAT formula in such a way is easily possible by the
following folklore lemma. For reference, a proof can be found in [2].

######  Lemma 6 (Lemma 1 in [2]).

The following transformation of a clause with only positive or only negative
literals, respectively, preserves the satisfiability of the clause ($y$ is a
new variable and $\mathtt{false}$ is the constant value false):

$\displaystyle
x_{i}\\!\lor\\!x_{j}\\!\lor\\!x_{k}\Rightarrow\\!\begin{cases}x_{k}\\!\lor\\!y\lor\mathtt{false}&\\!\text{(i)}\\\
x_{i}\\!\lor\\!x_{j}\\!\lor\\!\neg y&\\!\text{(ii)}\end{cases}$
$\displaystyle\neg x_{i}\\!\lor\\!\neg x_{j}\\!\lor\\!\neg
x_{k}\Rightarrow\\!\begin{cases}\neg x_{i}\\!\lor\\!\neg
x_{j}\\!\lor\\!y&\\!\text{(iii)}\\\ \neg x_{k}\\!\lor\\!\neg
y\\!\lor\\!\mathtt{false}&\\!\text{(iv)}\end{cases}$

Additionally to modifying the formula in the way described by Lemma 6 we also
ensure that the last clause in the formula is one containing only positive
literals, i.e., a clause with one or two literals both positive. If no such
clause exists, we simply create a clause of size one and a new variable that
is only present in this clause. In all following sections we assume that the
given 3SAT formula has been transformed as in Lemma 6 and that the last clause
has only positive literals.

To better illustrate the rather complex construction we developed a tool to
procedually generate a configuration from a given 3SAT formula. The code can
be found online333https://gitlab.com/fklute/segment-folding as well as a video
showing some simple examples444https://drive.google.com/file/d/1ythWVL1Wav-
uODUFAdKG4xEXOWxDK9zx/view?usp=sharing.

###  3.1 Overview

Figure 2: Overview of the reduction. Note that the lengths are not up to
scale.

We first give a brief overview of the reduction. Let $F(x_{1},\dots,x_{n})$ be
a 3SAT formula. As usual, our reduction will construct variable and clause
gadgets using $F(x_{1},\dots,x_{n})$ in a way so that any solution must first
fold all variable gadgets. In each such gadget we will have the choice to fold
one of two segments as the first one in the sequence, which will in turn
encode the truth value of a variable. The folds themselves will shift the
position of some literal segments. These segments will enable the folding of a
clause gadget if and only if the truth assignment of the associated variable
satisfies the clause. Only after all variables are folded the clause gadgets
can be folded. This will be possible in the required number of steps if and
only if for each clause gadget at least one variable was folded in a way that
the corresponding literal segment was placed in the enabling part of the
clause gadget.

###  3.2 Global layout

We define a vertical line $\gamma$ and two horizontal lines $\kappa_{1}$ and
$\kappa_{2}$. We call the region between $\kappa_{1}$ and $\kappa_{2}$ and to
the right of $\gamma$ the _clause region_. The region above $\kappa_{1}$ and
to the left of $\gamma$ is the _literal region_ and the region below
$\kappa_{2}$ and to the left of $\gamma$ is the _variable region_. As the
names indicate, we will place the clause, literal, and variable gadgets in the
corresponding regions. Figure 2 presents an illustration, the details will
become clear in the following sections. Furthermore, we define $w_{C}$ as the
sum of the width of all clause gadgets and $m_{C}=w_{C}/2$.

###  3.3 Variable gadget

For each variable $x$ the corresponding variable gadget consists of thirteen
segments. We call these segments _true segment_ $t$, _false segment_ $f$,
_true helper_ $t_{h}$, _false helper_ $f_{h}$, _true blocker one_ $t_{b}^{1}$,
_true blocker two_ $t_{b}^{2}$, _true blocker three_ $t_{b}^{3}$, _false
blocker one_ $f_{b}^{1}$, _false blocker two_ $f_{b}^{2}$, _false blocker
three_ $f_{b}^{3}$, _next blocker one_ $b_{1}$, _next blocker two_ $b_{2}$,
and _next blocker three_ $b_{3}$. For a variable $x$ we denote with $S(x)$ the
set of the thirteen segments corresponding to this variable. The precise
positioning of them is shown in Figure 3.

Let $w_{g}$ be the horizontal distance between the $t_{h}$ and $f_{h}$
segment. For a variable $x$, the gadget $S(x)$ without the next blocker
segment $b_{2}$ has width $w_{x}=37/2w_{g}+w_{C}$ and constant height $h_{x}$.
Nearly all horizontal space is between the two helper segments and the true
and false segment. It includes the _literal strip_ of variable gadget
$S(x_{i})$, see the light-blue region in Figure 3. This strip has width
$w_{C}$.

Figure 3: A variable gadget. The literal strip is shown in lightblue. The
marked endpoints indicate that the corresponding segments are strictly
separable with a vertical line. Especially, they do not intersect, but are
separated by a small gap. Note that one cell of the lightgray grid has width
and height $w_{g}$. (The drawing is not up to scale.)

The key property of the placement of the segments is that if we start folding
$t$, the segment $t_{b}^{2}$ is stabbed by the segment $f$, forcing us to fold
($t_{b}^{1}$ and) $t_{h}$ before $f$. Symmetrically, folding first along $f$
forces to fold ($f_{b}^{1}$ and) $f_{h}$ before $t$.

It remains to explain the function of the three next blocker segments $b_{1}$,
$b_{2}$, and $b_{3}$ of a variable gadget $S(x_{i})$ and the placement of
$b_{2}$. These segments guarantee that no segment in the variable gadget
$S(x_{i+1})$ can be folded before all the segments in $S(x_{i})$ have been
folded along. The segment $b_{3}\in S(x_{i})$ is a long horizontal segment,
and above it lie the segments in
$S(x_{i+1})\setminus\\{b_{3}\in~{}S(x_{i+1})\\}$. As we will see, for each
variable gadget $b_{3}$ is the last segment to be folded, and it prevents
segments in $S(x_{i+1})$ from being folded before. The segment $b_{2}$ is
there to reset the following variable gadgets properly, i.e., it makes sure
the next variable is at the same distance of $\gamma$ as the ones before.

We now describe how the variable gadgets are placed relative to each other. We
begin with variable $x_{1}$ and place it such that the true segment $t\in
S(x_{1})$ is $d_{x}=10w_{g}$ units to the left of the vertical line $\gamma$
and the top-point of $t\in S(x_{1})$ is $(n-1)8h_{x}+7h_{x}$ units below the
horizontal line $\kappa_{2}$. The next variable gadgets
$S(x_{2}),\dots,S(x_{n})$ are placed to the left and above $S(x_{1})$ always
leaving $15d_{x}+6w_{g}+6w_{C}$ units of horizontal space between $t$ in
$S(x_{i-1})$ and the $t$ segment of $S(x_{i})$, as well as $2h_{x}$ units
vertical space between the upper end-point of $t\in S(x_{i-1})$ and the lower
end-point of $f\in S(x_{i})$. (Hence, for each variable $x_{i}$ the true
segment of its gadget $S(x_{i})$ is placed
$10w_{g}+(i-1)(15d_{x}+6w_{g}+6w_{C})$ units left of $\gamma$.) We place
$b_{2}\in S(x_{i})$ at $10d_{x}+5w_{C}$ horizontally to the left of $t\in
S(x_{i})$. Finally, $b_{3}$ is placed directly to the left of $b_{2}$ and
extended by $10w_{C}$ units to the left.

We now show that there are only four ways to fold a variable gadget.

######  Lemma 7.

Up to folding $t_{b}^{3}$ and $f_{b}^{3}$ there are exactly two ways in which
a variable gadget can be folded in thirteen steps, namely:

$\displaystyle t\rightarrow t_{b}^{1}\rightarrow t_{h}\rightarrow
t_{b}^{2}\rightarrow f\rightarrow f_{b}^{1}\rightarrow f_{h}\rightarrow
f_{b}^{2}\rightarrow b_{1}\rightarrow b_{2}\rightarrow b_{3}$ or
$\displaystyle f\rightarrow f_{b}^{1}\rightarrow f_{h}\rightarrow
f_{b}^{2}\rightarrow t\rightarrow t_{b}^{1}\rightarrow t_{h}\rightarrow
t_{b}^{3}\rightarrow b_{1}\rightarrow b_{2}\rightarrow b_{3}.$

Furthermore, $t_{b}^{3}$ and $f_{b}^{3}$ can be folded only after $t_{h}$,
respectively $f_{h}$, is folded and have to be folded before $b_{1}$ can be
folded.

###### Proof.

Let
$S=\\{t,t_{h},t_{b}^{1},t_{b}^{2},t_{b}^{3},f,f_{h},f_{b}^{1},f_{b}^{2},f_{b}^{3},b_{1},b_{2},b_{3}\\}$
be the segments of a variable gadget constructed as above. Then the only three
non stabbing segments are $b_{2}$, $t$ and $f$. Notice that $b_{2}$ cannot be
folded before $b_{1}$ and $b_{3}$, since $b_{1}$ would intersect $b_{3}$ after
the folding. By Observation 4 this means the only possible folds are along $t$
and $f$, respectively.

Without loss of generality assume we first fold $t$. Let $S^{\prime}$ be the
new set of segments. Note that, since $t$ was not stabbing and no crossings
were created, by Observation 3, we also did not create a new segment and no
two segments are sharing a common supporting line. Identify the segments in
$S$ with their reflected counterparts in $S^{\prime}$. Then $f$ and $b_{1}$
are now stabbing $t_{b}^{2}$, but $t_{b}^{1}$ does not stab any segment
anymore. All other segments are still stabbing the same segments as before.
Hence the only possible fold is along the supporting line of $t_{b}^{1}$. By
the same argumentation we get that the following folds must be in order
$t_{h}$, $t_{b}^{2}$, $f$, $f_{b}^{1}$, $f_{h}$, $f_{b}^{2}$, $b_{1}$, and
$b_{3}$. The segment $b_{2}$ cannot be folded early as this would lead to
$b_{1}$ forming a crossing with $b_{3}$, which is not allowed by Observation
3. Finally, $t_{b}^{3}$ can never be folded before $t_{h}$ has been folded by
Observation 4 and folding it at any point after that has all remaining
segments of the variable gadget in one half-plane relative to the supporting
line of $t_{b}^{3}$. Hence, the relative positions of the remaining segments
in the variable gadget do not change. The same can be argued for $f_{b}^{3}$
relative to $f_{h}$. We can argue in the same manner for the folding sequence
starting with $f$. ∎

Next we will show that the folding sequences of length $13n$ for the variable
gadgets all fold the gadgets in order of the corresponding indices.

######  Lemma 8.

Let $x_{1},\dots,x_{n}$ be the variables of a 3SAT formula and consider the
variable gadgets $S(x_{1}),\dots,S(x_{n})$ as above, then the variable gadgets
can be folded in $13n$ steps if and only if they are folded in order of their
indices.

###### Proof.

The leftmost point of any segment in $S(x_{1})\setminus\\{b_{2},b_{3}\in
S(x_{1})\\}$ and the rightmost point of any segment in $S(x_{2})$ are more
than $5w_{C}$ apart. Consequently, any fold along a vertical segment in
$S(x_{1})$ leaves the segments in $S(x_{2}),\dots,S(x_{n})$ on the same half-
plane relative to the remaining segments in $S(x_{1})$. For the folds along
horizontal segments, the topmost point of any segment in $S(x_{1})$ and the
bottommost point of any segment in $S(x_{2})$ are at least $7h_{x}$ units
apart. Since there are only seven horizontal segments, it is clear that no
fold along a horizontal segment in $S(x_{1})$ can lead to a segment in
$S(x_{1})$ stabbing a segment in $S(x_{2})\cup\dots\cup S(x_{n})$.

From Lemma 7 it follows that folding the variable gadgets in the order of the
corresponding indices gives a fold in $13n$ steps, as the sequence of 13 folds
chosen for one gadget does not interfere with any other gadget.

It remains to argue the reverse direction. Assume we have a sequence of $13n$
folds such that some segment in $s_{i+1}\in S(x_{i+1})$ is folded before some
segment $s_{i}\in S(x_{i})$. We immediately see that $s_{i+1}$ cannot be a
vertical segment, since those can only be folded after $b_{3}\in S(x_{i})$ was
folded. However, by Lemma 7, the first segment to be folded in $S(x_{i+1})$ is
a vertical segment. ∎

###  3.4 Literal gadgets

As will be explained in Subsection 3.5 the clause gadget requires a specific
fold along a vertical line. These folds are going to be done along supporting
lines of segments corresponding to literals. Here, we only describe the
literal gadgets and their initial placement. The functioning will become
apparent in the then following sections. We include a blocker segment that
ensures all segments in variable gadgets must be folded before any segment in
a literal gadget.

Let $c_{j}$ be a clause and $x_{i}$ a variable that occurs in $c_{j}$ and
denote with $z_{i,j}$ the corresponding literal. For $z_{i,j}$ we create one
vertical segment $z\in S(z_{i,j})$ and one horizontal segment $b\in
S(z_{i,j})$. Intuitively, the former segment will be the one that enables the
folding of a clause gadget if it is folded into the respective clause’s good
zone, while the latter segment is needed to partially fix the order in which
the literal and clause gadgets can be folded. In the following we call $z\in
S(z_{i,j})$ the _literal segment_ of $z_{i,j}$ and $b\in S(z_{i,j})$ the
_literal blocker_ of $z_{i,j}$.

We continue by placing the literal segments and blockers. Roughly, for each
literal $z_{i,j}$ corresponding to an occurrence of variable $x_{i}$ in clause
$c_{j}$, the segments in $S(z_{i,j})$ are placed above $\kappa_{1}$ and inside
the literal strip of the gadget $S(x_{i})$ that corresponds to variable
$x_{i}$, see the corresponding light-blue strip in Figure 3.

In the following fix one literal $z_{i,j}$ and its literal segment $z\in
S(z_{i,j})$ and literal blocker $b\in S(z_{i,j})$. First, we describe the
horizontal position of $z$. We place $z$ with an offset to the true segment
$t$ of $S(x_{i})$ of $(16+\frac{1}{4})w_{g}+(j-1)w_{c}$ if $x_{i}$ appears
positive in $c_{j}$ and at $(20+\frac{3}{4})w_{g}+(j-1)w_{c}$ if $x_{i}$
appears negated in $c_{j}$. (This means that if $z$ is positive it is placed

$\displaystyle 10w_{g}+(i-1)(15d_{x}+6w_{g}+6w_{C})+(16+1/4)w_{g}+(j-1)w_{C}$
$\displaystyle=(i-1)15d_{x}+(6i+20+1/4)w_{g}+(j+5)w_{C}$

units to the left of $\gamma$ and, similarly, if it is negative it is placed
$(i-1)15d_{x}+(6i+24+\frac{3}{4})w_{g}+(j+5)w_{C}$ units to the left of
$\gamma$.) Finally, to avoid multiple literal segments being placed at the
same $x$-coordinate, we give $z$ a negative horizontal offset
$\delta=\frac{1}{100}w_{g}$ if $z_{i,j}$ if it is the literal with smallest
index $i$ in the clause, and a positive horizontal offset of $\delta$ if the
literal has the largest index $i$ in the clause.

Second, we need to position $z$ vertically and compute its length. The
bottommost point of $z$ is placed at $w_{g}$ units above $\kappa_{1}$. The
length of $z$ is given as $2j\cdot w_{g}$ if $z_{i,j}$ is a positive literal
and $2j\cdot w_{g}+w_{g}$ if $z_{i,j}$ is a negative literal. It remains to
describe the positioning of the literal blocker $b\in S(z_{i,j})$. We place
$b$ at $\frac{1}{2}w_{g}$ units above $z$ and its midpoint at the
$x$-coordinate coinciding with the horizontal position of $z$. Again, to avoid
colinearities, we give $b\in S(z_{i,j})$’s verical position an offset $\delta$
depending on if $i$ is the lowest, middle, or highest index in clause $c_{j}$.
Finally, we set $b$ to be $\frac{1}{100}w_{g}$ units long.

######  Lemma 9.

Let $F(x_{1},\dots,x_{n})$ be a 3SAT formula and consider the variable gadgets
$S(x_{1}),\dots,S(x_{n})$ and literal gadgets $S(z_{i,j})$ as above, then for
$j\in\\{1,\ldots,m\\}$ the segments in $S(z_{i,j})$ with
$i\in\\{1,\ldots,n\\}$ are folded after all segments in
$\cup_{j^{\prime}<j}S(z_{i,j^{\prime}})$. Moreover, for each
$j\in\\{1,\ldots,m\\}$ literal gadgets $S(z_{i,j})$ corresponding to negative
literals in $c_{j}$ are folded before the ones corresponding to positive
literals.

###### Proof.

A literal segment $z\in S(z_{i,j})$ can never be folded before $b\in
S(z_{i,j})$ by Observation 4. Moreover, $b$ stabs every literal segment in
$\cup_{j^{\prime}<j}S(z_{i,j^{\prime}})$ by construction. Hence, again by
Observation 4, $b$ cannot be folded before all literal segments in
$\cup_{j^{\prime}<j}S(z_{i,j^{\prime}})$ and their respective literal blockers
are folded. Finally, if $z_{i,j}$ is a positive literal in clause $c_{j}$ its
literal blocker $b$ stabs any literal segment $z^{\prime}\in
S(z_{i^{\prime},j})$ where $x_{i^{\prime}}$ occurs negated in $c_{j}$.
Consequently, by Observation 4, the segments in $S(z_{i,j})$ are folded after
the literal segment in $S(z_{i^{\prime},j})$. ∎

To block the segments in literal gadgets to be folded before we have folded
all segments in variable gadgets we introduce one vertical segment $b_{z}$.
Horizontally we place it $11d_{x}+5w_{C}$ units of horizontal distance to the
left of $t\in S(x_{n})$. (Hence, $b_{z}$ is placed
$10w_{g}+(n-1)(15d_{x}+6w_{g}+6w_{C})+11d_{x}+5w_{C}$ units to the left of
$\gamma$.) Vertically we put its bottommost point on $\kappa_{2}$ and extend
it vertically by $(2m-1)h_{c}\cdot(3m+1)\cdot w_{g}$ units where
$h_{c}=\frac{59}{2}w_{g}$ is the height of a clause gadget which we introduce
in the following Subsection 3.5.

The following observation is immediate after realizing that $b_{z}$ stabs the
blocker $b_{3}$ of variable $x_{n}$.

######  Observation 10.

Let $F(x_{1},\dots,x_{n})$ be a 3SAT formula and consider the variable gadgets
$S(x_{1}),\dots,S(x_{n})$ and literal gadgets $S(z_{i,j})$ as above, then for
all literals $z_{i,j}$ the segments in $S(z_{i,j})$ are folded after all
segments in $S(x_{1}),\ldots,S(x_{n})$.

###  3.5 Clause Gadget

For each clause $c_{j}$ we introduce a clause gadget $S(c_{j})$ consisting of
four _clause segments_ $c^{1},c^{2},c^{3}$, and $c^{4}$ and one _clause
blocker_ $b$. Each clause gadget is confined to a rectangular area with a
width $w_{c}$ of $9w_{g}$ and a height $h_{c}$ of $\frac{59}{2}w_{g}$. In the
following, we describe the positioning of all the segments in a clause gadget
relative to its top left corner, compare also Figure 4(a) and Figure 5(a).
Segment $c^{1}$ has its left endpoint $\frac{9}{2}w_{g}$ units from the left
and $4w_{g}$ units from the top and its right endpoint at $6w_{g}$ units from
the left and $\frac{5}{2}w_{g}$ units from the top. The second segment $c^{2}$
is positioned with both its endpoints at the same $x$-coordinate of
$8w_{g}+\frac{1}{8}w_{g}$ and its upper endpoint is at zero, while its lower
endpoint is also at $\frac{5}{2}w_{g}$ units from the top. Segment $c^{3}$ has
a length of $\frac{3}{2}w_{g}+\frac{1}{10}w_{g}$ to account for the offsets in
the literal gadgets an is positioned $5w_{g}$ units from the top with its left
endpoint at $7w_{g}$. Finally, segment $c^{4}$ has its upper end point
$\frac{11}{2}w_{g}$ units from the top and its lower endpoint at
$\frac{25}{2}w_{g}$ units from the top.

It remains to place the blocker $b\in S(c_{j})$. This segment has its right
end point at $\frac{1}{4}w_{g}$ units from the top and $3w_{g}$ units from the
left, relative to clause gadget $S(c_{j})$. It then extends $12w_{g}$ units to
the left, i.e. $9w_{g}$ units of $b$ lie outside of the clause gadget
$S(c_{j})$.

Figure 4: Clause gadget folded along a literal gadget corresponding to a
positive literal. Figure 5: Clause gadget folded along a literal gadget
corresponding to a negative literal.

Next, we consider the possible folding sequences of a clause gadget $S(c_{j})$
for a clause $c_{j}$. First, we observe that of the five segments none can be
folded without some additional sixth segment. For $c^{1}$, $c^{2}$, $c^{4}$,
and $b$ in $S(c_{j})$ this can be seen immediately by Observation 4 as they
each stab another segment. For $c^{3}$, observe that folding along it would
produce an intersection between segment $c^{1}$ and $c^{4}$ which is forbidden
by Observation 3.

In the following we call the vertical strip in $S(c_{j})$ in between $6w_{g}$
to $7w_{g}$, but excluding the vertical lines at $6w_{g}$ and $7w_{g}$ its
good zone (see the green strips in Figure 4(a) or 5(a)). Moreover, we call the
region from $w_{g}$ to $3w_{g}$ the _bad zone_ of the gadget. This region is
shaded in red in Figure 4 and 5. We now show under which condition it is
actually possible to fold the gadget.

######  Lemma 11.

A clause gadget $S(c_{j})$ with segments $c^{1}$,$c^{2}$,$c^{3}$,$c^{4}$, and
$b$ as above, in a setting where no horizontal segment can be folded, can be
folded in five steps if and only if there is a segment $s$ whose supporting
line goes along its good zone. Moreover, in steps one and two the folds are
$c^{1}$ followed by $c^{2}$ and the last fold is along $c^{4}$ or $b$.

###### Proof.

We first show how $S(c_{j})$ can be folded if the supporting line of some
segment lies in its good zone at either $6.25w_{g}$ or $6.75w_{g}$ (this will
later be the positions of the literal segments introduced in Subsection 3.4).
Figure 4 details the first two folds if such a vertical segment is in the
middle of the darkgreen strip ($6.25w_{g}$) and Figure 5 shows the same for a
segment in the middle of the lightgreen strip ($6.75w_{g}$). After folding
along any of these strips we next have to fold along segment $c^{1}\in
S(c_{j})$ by the same arguments as before. This leads to the configurations
shown in Figure 4(c) and 5(c). Here, we are forced to first fold $c^{2}\in
S(c_{j})$. The only other non-stabbing segment would be to fold along
$c^{3}\in S(c_{j})$, but this would lead to an intersection between $c^{2}$
and $b\in S(c_{j})$ which is not allowed by Observation 3. Finally, we fold
the clause segments $c^{3}$ and $c^{4}$ of $S(c_{j})$ as well as $b\in
S(c_{j})$ in any order such that $c^{3}$ is folded before $c^{4}$. Hence, we
were able to fold $S(c_{j})$ in five steps as desired. With the same
argumentation we can fold $S(c_{j})$ for any other supporting line going
through the good zone of the gadget.

Now assume we could fold $S(c_{j})$ without ever folding along a line going
through its good zone. Clearly if no supporting line lies in the strip between
the pairs of clause segments $c^{1}$, $c^{4}$ and $c^{2}$, $c^{3}$ we can
never fold any of the clause segments. Moreover, if a supporting line would
coincide with the vertical line at $6w_{g}$ or $7w_{g}$ it would intersect
$c^{1}$ or $c^{3}$ and hence, by Observation 4 we could not fold this line. ∎

It remains to position the clause gadgets relative to each other. Recall, that
a clause has width $w_{c}=9w_{g}$ and height $h_{c}=\frac{25}{2}w_{g}$. Also
recall, that the leftmost point of a clause gadget is $w_{g}$ units left of
its bad zone and the rightmost point $w_{c}$ units from its leftmost point.
Its topmost point is at the same point as the topmost point of its clause
segment $c^{2}$ and its bottommost point at distance $h_{c}$ from its topmost
point. Moreover, the first clause gadget $S(c_{1})$ has no clause blocker. We
position $S(c_{1})$ such that its leftmost point lies on $\gamma$ and its
bottommost point is $(m-1)2h_{c}$ units above $\kappa_{2}$ and $h_{c}$ units
below $\kappa_{1}$. The next clause $S(c_{2})$ is placed $h_{c}$ units below
the bottommost point of $S(c_{1})$ and such that its leftmost point aligns
with the rightmost point of $S(c_{1})$. Consequently, the clause blocker $b\in
S(c_{2})$ is stabbed by the clause segments $c^{2},c^{4}\in S(c_{1})$.
Continuing in this fashion we place all $m$ clause gadgets. Note, that the
bottommost point of $S(c_{m})$ precisely aligns with $\kappa_{2}$ and that
there is $h_{c}$ units of vertical space between the topmost point of
$S(c_{j})$ and $S(c_{j-1})$ for any $1<j\leq m$ and that each clause blocker
$b\in S(c_{j})$ for $1<j\leq m$ is stabbed by the clause segments
$c^{2},c^{4}\in S(c_{j-1})$. We now state the same ordering lemma for the
clauses as for the variables, assuming that there is one vertical segment
whose supporting line lies inside the good zone for each clause gadget.

######  Lemma 12.

Let $F(x_{1},\dots,x_{n})$ be a 3SAT formula and consider the set of segments
$S$ for clauses $c_{j}\in F(x_{1},\ldots,x_{n})$ as defined above and assume
that for each clause gadget $S(c_{j})$ corresponding to a clause $c_{j}$ there
is exactly one vertical segment whose supporting line lies inside the good
zone of $S(c_{j})$, then the clause gadgets can only be folded in order
$S(c_{m}),\ldots,S(c_{1})$.

###### Proof.

As just observed the clause blocker $b\in S(c_{j})$ is stabbed by the clause
segments $c^{2},c^{4}\in S(c_{j-1})$ for every $1<j\leq m$. Moreover, this
means that the vertical segment in the good zone of each $S(c_{j-1})$ stabs
$b\in S(c_{j})$. Hence, with Lemma 11, the only segment we can fold in step
one is the vertical segment whose supporting line lies in the good zone of
$S(c_{m})$. Crucially, also by Lemma 11, the last segment we fold is either
$b$ or $c^{4}$. Moreover, after the fold along $c^{1}$ segment $c^{4}$ is at
the same $x$-coordinates as $b$ and hence any vertical segment that was
stabbing $b$ is now also stabbing $c^{4}$. Consequently, we can only fold
$S(c_{m-1})$ once all segments in $S(c_{m})$ are folded.

To complete the proof observe that all segments in any $S(c_{j})$ for $1\leq
j<m$ are completely in one half-plane relative to the supporting lines of
segments in $S(c_{m})$ when we fold along them. Hence, their relative
positions did not change. ∎

###  3.6 Correctness

It remains to argue the correctness of our reduction. Theorem 5 then follows
directly from Lemma 15.

######  Lemma 13.

Given a 3SAT formula $F(x_{1},\ldots,x_{n})$, let $S(x_{1}),\dots,S(x_{n})$ be
the variable gadgets constructed as above. Then, after folding
$S(x_{1}),\dots,S(x_{i})$, the horizontal distance between $t\in S(x_{i+1})$
and $\gamma$ is $d_{x}$.

###### Proof.

First consider the fold along the segments in $S(x_{1})$. By Lemma 7 we know
there are four sequences of folds we have to consider. We first show that the
statement initially holds for folding all segments in $S(x_{1})$.

Let $h(s,t)$ be the horizontal distance between the two vertical segments or
lines $s$ and $t$, and let $h^{\prime}(s,t)$ be the horizontal distance
between segments or lines $s$ and $t$ after
$S(x_{1})\setminus\\{b_{2},b_{3}\\}$ was folded.

We start by showing that, after folding all segments in
$S(x_{1})\setminus\\{b_{2},b_{3}\\}$,
$h^{\prime}(b_{2},\gamma)=10w_{g}+w_{C}$. Note that for the horizontal
distance the folds along horizontal segments do not matter. Hence, it suffices
to consider a sequence of folds starting with $t\in S(x_{1})$ and one starting
with $f\in S(x_{1})$.

We start with $t\in S(x_{1})$, and we use that $h(t,b_{1})=1w_{g}$:

$\displaystyle h^{\prime}(b_{2},\gamma)=h(b_{2},\gamma)$
$\displaystyle-2h(t,\gamma)$ $\displaystyle-2(h(t_{h},\gamma)-2h(t,\gamma))$
$\displaystyle-2(h(f,\gamma)-4w_{g})$
$\displaystyle-2(h(f_{h},\gamma)-2h(t,\gamma)-2w_{g})$
$\displaystyle-2(h(b_{1},\gamma)-4w_{g}).$

Since $h(t,\gamma)=10w_{g}$ and $h(f,\gamma)=12w_{g}$, we get

$\displaystyle h^{\prime}(b_{2},\gamma)=h(b_{2},\gamma)$
$\displaystyle-20w_{g}$ $\displaystyle-2h(t_{h},\gamma)+40w_{g}$
$\displaystyle-16w_{g}$ $\displaystyle-2h(f_{h},\gamma)+44w_{g}$
$\displaystyle-2h(b_{1},\gamma)+8w_{g}$ $\displaystyle=h(b_{2},\gamma)$
$\displaystyle-2h(t_{h},\gamma)-2h(f_{h},\gamma)$
$\displaystyle-2h(b_{1},\gamma)+56w_{g}.$

For the sequence starting with $f\in S(x_{1})$

$\displaystyle h^{\prime}(b_{2},\gamma)=h(b_{2},\gamma)$
$\displaystyle-2h(f,\gamma)$ $\displaystyle-2(h(f_{h},\gamma)-2h(f,\gamma))$
$\displaystyle-2(h(t,\gamma))$ $\displaystyle-2(h(t_{h},\gamma)-2h(f,\gamma))$
$\displaystyle-2(h(b_{1},\gamma)-2w_{g}).$

Since $h(t,\gamma)=10w_{g}$ and $h(f,\gamma)=12w_{g}$, we get

$\displaystyle h^{\prime}(b_{2},\gamma)=h(b_{2},\gamma)$
$\displaystyle-24w_{g}$ $\displaystyle-2h(f_{h},\gamma)+48w_{g}$
$\displaystyle-20w_{g}$ $\displaystyle-2h(t_{h},\gamma)+48w_{g}$
$\displaystyle-2(h(b_{1},\gamma)+4w_{g}$ $\displaystyle=h(b_{2},\gamma)$
$\displaystyle-2h(t_{h},\gamma)-2h(f_{h},\gamma)-2h(b_{1},\gamma)+56w_{g}.$

It follows that for both sequences the distance between $b_{2}$ and $\gamma$
will be equal. Furthermore, we can compute this distance. Since
$h(b_{1},\gamma)=11w_{g}$, $h(f_{h},\gamma)=h(t_{h},\gamma)+w_{g}$, and
$h(b_{2},\gamma)=11d_{x}+5w_{c}$ arrive to

$\displaystyle h^{\prime}(b_{2},\gamma)$
$\displaystyle=h(b_{2},\gamma)-4h(t_{h},\gamma)+32w_{g}$
$\displaystyle=11d_{x}+5w_{C}-4(d_{x}+h(t,t_{h}))+32w_{g}$
$\displaystyle=10d_{x}+2w_{g}+5w_{C}-4(14+w_{C})$
$\displaystyle=4d_{x}+6w_{g}+w_{C}.$

To get the lemma, note that since the true segment $t\in S(x_{2})$ and $b_{2}$
were always in the same half-plane in the folding sequences above, the
distance between $t\in S(x_{2})$ and $b_{2}$ did not change. Hence, the
distance between $t\in S(x_{2})$ and $\gamma$ after folding along all segments
in $S(x_{1})$ is

$\displaystyle h(b_{2},t)-h^{\prime}(b_{2},\gamma)$
$\displaystyle=5d_{x}+6w_{g}+w_{C}-(4d_{x}+6w_{g}+w_{C})=d_{x}.$

Since by Lemma 8 the variable gadgets $S(x_{1}),\dots,S(x_{n})$ can only be
folded in order of their indices the above calculation holds for any
$S(x_{i})$ and $S(x_{i+1})$ in such a sequence. ∎

######  Lemma 14.

Given a 3SAT formula $F(x_{1},\ldots,x_{n})$, let $S$ be the set of segments
constructed by the reduction. Let $\mathcal{S}$ be a folding sequence of the
variable gadgets up to $S(x_{i-1})$. Let $S^{\prime}$ be the segments after a
fold along $s\in\\{t,f\\}\subset S(x_{i})$. If $s=t$, then for every literal
gadget $S(z_{i,j})$ with clause $c_{j}\in F(x_{1},\dots,x_{n})$ we have that
$S^{\prime}(z_{i,j})$ is in the good zone of $S^{\prime}(c_{j})$ if $z_{i,j}$
is a positive literal, and in the bad zone otherwise. If instead $s=f$, then
for every literal gadget $S(z_{i,j})$ with clause $c_{j}\in
F(x_{1},\dots,x_{n})$ we have that $S^{\prime}(z_{i,j})$ is in the good zone
of $S^{\prime}(c_{j})$ if $z_{i,j}$ is a negative literal, and in the bad zone
of $S^{\prime}(c_{j+1})$ otherwise. Moreover, it is the only literal segment
reflected to this coordinate.

###### Proof.

For the proof we only need to consider horizontal distances, and thus, folds
along vertical segments. Let us first not consider the $\delta$ offsets. By
Lemma 13 we know that the distance between the clauses and $t\in S(x_{i})$
remains $d_{x}=10w_{g}$.

We have to consider four cases. First let $S^{\prime}$ be the set of segments
after a fold along $t\in S(x_{i})$. Then, any positive literal segment
$S(z_{i,j})$ is reflected to a distance $(16+\frac{1}{4})w_{g}+(j-1)w_{c}$
from $t$. At the same time the good zone of $c_{j}$ starts at distance
$16w_{g}+(j-1)w_{c}$ from $t$ and spans $w_{g}$ units. Hence the segment is
reflected into the good zone as desired. For a negative literal segment
$S(z_{i,j})$ is reflected to a distance

$\displaystyle\left(20+\frac{3}{4}\right)w_{g}+(j-1)w_{c}$
$\displaystyle=\left(20+\frac{3}{4}\right)w_{g}+j\cdot w_{c}-9w_{g}$
$\displaystyle=\left(11+\frac{3}{4}\right)w_{g}+j\cdot w_{c}$

from $t$. At the same time the bad zone of $c_{j+1}$ starts at distance
$10w_{g}+j\cdot w_{c}$ from $t$ and spans $4w_{g}$ units. Hence the segment is
reflected into the bad zone of the next clause gadget.

Now consider a fold along $f\in S(x_{i})$ segment. Then for a positive literal
$z_{i,j}$ the literal segment of $S(z_{i,j})$ is reflected to
$(16+\frac{1}{4})w_{g}+(j-1)w_{c}-4w_{g}=(12+\frac{1}{4})w_{g}+(j-1)w_{c}$ to
the right of $t\in S(x_{i})$ and the bad zone of $S(c_{j})$ starts at distance
$10w_{g}+(j-1)w_{c}$ from $t$ and spans $4w_{g}$ units. As desired the segment
is reflected to the bad zone. Finally consider a negative literal $z_{i,j}$,
then the literal segment of $S(z_{i,j})$ is reflected to
$(16+\frac{3}{4})w_{g}+(j-1)w_{c}$ to the right of $t\in S(x_{i})$ and the
good zone of $S(c_{j})$ starts at distance $16w_{g}+(j-1)w_{c}$ from $t$ and
spans $w_{g}$ units. As desired, the segment is reflected to the good zone of
$S(c_{j})$.

So far all literal segments belonging to the same clause $c_{j}$ are reflected
to the same coordinates in the good and bad zones. Now consider the $\delta$
offset we added depending on the index of the variable. Since we can assume
that no variable appears twice in a clause the indices $i$ of all three
literals are different. Hence, to exactly one we add $\delta$, to one we do
not add or subtract it and from one we subtract $\delta$. Since $\delta$ is
greater zero, but smaller than $\frac{1}{4}w_{g}$, we get that the three
literal segments for a clause $c_{j}$ are still inside the good and bad zone,
but never at the same coordinate. ∎

The reduction can be computed in polynomial time in $n$: for a given 3SAT
formula $F(x_{1},\ldots,x_{n})$, we can construct the set $S$ of segments in
polynomial time in $n$ using the specified coordinates (if we want integer
coordinates we can set $w_{g}=400$). Theorem 5 follows from the next lemma.

######  Lemma 15.

Let $F(x_{1},\dots,x_{n})$ be a formula of a 3SAT instance and $S$ the set of
segments constructed from $F$ as above, then $F$ is satisfiable if and only if
$S$ can be folded in $\left|S\right|$ steps.

###### Proof.

Let $S$ be the set of segments constructed as above from a 3SAT formula
$F(x_{1},\dots,x_{n})$, and let $\mathcal{S}$ be a folding sequence of length
$\left|S\right|$, folding $S$. Combining Lemmas 8, 11 and 12, as well as
Observation 10, we get that in $S$ the variable gadgets must all be folded
first, then the literal and clause gadgets. Furthermore, by Lemma 7, each fold
of a variable gadget starts with the $t$ or $f$ segment for each variable. By
Lemma 14 we know that a literal segment gets reflected into the good zone of a
clause if and only if it appears positive and the $t$ segment is folded first
or it appears negated and the $f$ segment of the corresponding variable is
folded first. Additionally, by Lemma 11, no clause gadget can be folded in the
required number of steps if there is no segment inside its good zone.
Moreover, by Lemma 9 the literal segments corresponding to literals of one
clause $c_{j}$ have to be folded before any literal segment corresponding to a
literal in clause $c_{j-1}$. Since by Lemma 11 the last segment when folding a
clause is $b$ or the, by then, parallel segment $c^{4}$ we find that the
clause and literal gadgets are folded ordered by the index of their
corresponding clause from $m$ to $1$. Finally observe that in such a folding
sequence no two segments ever cross.

Two technicalities remain, for which the two transformations done to the 3SAT
formula are crucial. First, as the last clause $c_{m}$ is a positive one, it
cannot happen that a literal segment is ever reflected to a position that
would be the bad zone of clause $c_{m+1}$. Second, we can only partially fix
the order in which the literal segments of one clause are folded. Observe,
that if $|S|$ folds are sufficient there exists a sequence of folds along
literal segments such that either the segment we fold is the one that breaks
the cyclic dependencies in the clause gadget or the segment is on the convex
hull. Hence, for the latter discussed reverse direction in which we are given
a satisfying assignment, a folding sequence in $|S|$ steps is easy to
construct. It remains to proof that we can never fold along a segment such
that two literal segments are reflected ontop of each other. Here, the
transformation by Lemma 6 makes the argument much simpler, as we only have to
consider clauses containing two negative or two positive literals.

We begin by assuming that the next clause gadget that we can fold is
$S(c_{j})$ and consider the two cases if the first literal segment folded that
lies in the good zone of $S(c_{j})$ corresponds to a positive or a negative
literal. In the following we measure distances from the rightmost point of
$S(c_{j-1})$, hence the bad zone of $S(c_{j})$ always stars at at $w_{g}$
units. First, assume this first literal segment $z$ corresponds to a positive
literal. Then, there is at most one other literal segment remaining as literal
segments corresponding to negative literals are folded before the ones
corresponding to positive literals by Lemma 9 and no clause has three positive
literals by Lemma 6. Let $z^{\prime}$ be this remaining literal segment
corresponding to a positive literal. If $z^{\prime}$ was reflected to the bad
zone of $S(c_{j})$ no alignment can happen as $z^{\prime}$ is only folded
after all segments in $S(c_{j})$ are folded. In the case that $z^{\prime}$ was
initially reflected to the good zone of $S(c_{j})$ it is in the following
reflected at most along the segments $c^{2}\in S(c_{j})$. After the fold along
$c^{2}$ the segment $z^{\prime}$ is at horizontal position
$(2+\frac{1}{2})w_{g}$. By Lemma 14 the other literal segments in the bad zone
of $S(c_{j})$ are at $(1+\frac{3}{4})w_{g}$. Hence, $z^{\prime}$ is on the
convex hull and can be folded, by Observation 2, before any following literal
segment as desired.

Second, assume the first literal segment $z$ corresponds to a negative
literal. Here we have to consider at most two more existing literal segments.
Assume that only one more literal segment $z^{\prime}$ exists. In case
$z^{\prime}$ corresponds to a positive literal we are done as above. If
$z^{\prime}$ corresponds to a negative literal we can nearly argue as before,
with the difference that $z_{n}$ is reflected along $c^{2}$ and $c^{3}$ of
$S(c_{j})$ to be reflected to position $(2+\frac{1}{2})w_{g}$. Note, that it
could also be folded before $c^{3}$ in which case $z_{n}$ is just on the
convex hull of the remaining segments. In the following assume $c_{j}$ has
three literals. Then, two cases are to be considered, either the two remaining
literal segments both correspond to positive literals or to a positive and a
negative literal. We begin with the latter and let $z_{p}$ and $z_{n}$ be the
literal segments corresponding to a positive and a negative literal of $c_{j}$
respectively. If $z_{n}$ was initially reflected to the bad zone of
$S(c_{j+1})$ we get that after folding at $z$ the segment $z_{n}$ is at
$(2+\frac{3}{4})w_{g}$. Since $z_{n}$ has to be folded before $z_{p}$ this is
not a problem if $z_{p}$ lies in the bad zone of $S(c_{j})$. In case $z_{p}$
lies in the good zone though it will be reflected to $-\frac{3}{4}w_{g}$ after
folding along $z_{n}$. Consequently, $z_{p}$ will then stab the segment
$c^{3}\in S(c_{j-1})$ and we cannot proceed as no literal segment in the good
zone of $S(c_{j-1})$ can be folded before $z_{p}$ is folded. Hence, $z_{n}$
had to be folded before $z$. Now, consider that $z_{n}$ was initially also in
the good zone of $S(c_{j})$, but then after folding along $z$ we find that
$z_{n}$ is on the convex hull of the remaining segments and furthermore it has
to be folded before $z_{p}$ by Lemma 9. The remaining segment $z_{p}$ can then
be treated as above in the case of just one further literal segment. Lastly,
we consider the case that both remaining literal segments correspond to
positive literals in $c_{j}$ and let $z_{1}$ and $z_{2}$ be the two literal
segments. If both are initially in the bad zone of $S(c_{j})$ no alignments
are possible as they are both only folded after all segments in $S(c_{j})$. If
both are initially in the good zone of $S(c_{j})$ we can treat them as if only
one literal segment corresponding to a positive literal was remaining.
Finally, assume that, w.l.o.g., $z_{1}$ was initially reflected to the good
zone of $S(c_{j})$ and $z_{2}$ to the bad zone. Now, $z_{1}$ is either folded
before $z_{2}$ or is as above reflected along $c^{2}\in S(c_{j})$ and
$c^{3}\in S(c_{j})$ to $(2+\frac{1}{2})w_{g}$. The only remaining case is that
$z_{2}$ is folded before $z_{1}$, but then similarly to above $z_{1}$ is
reflected to a position of $-(1+\frac{3}{4})w_{g}$ and intersects the segment
$c^{3}\in S(c_{j})$. As a result, we find a satisfying assignment of the
variables of $F$ by simply setting $x_{i}$ to true if in $\mathcal{S}$ the
true segment $t\in S(x_{i})$ was folded before $f\in S(x_{i})$ and to false if
the converse holds.

For the reverse direction, let $F(x_{1},\dots,x_{n})$ be again a 3SAT formula
and $\mathcal{F}$ a fulfilling assignment. Now let $S$ be the set of segments
constructed as above. We construct a folding sequence $\mathcal{S}$ as
follows. For every variable gadget $S(x_{i})$ pick $t\in S(x_{i})$ to be
folded first if $x_{i}$ is set to true in $\mathcal{F}$ and pick $f\in
S(x_{i})$ otherwise. It follows from Lemmas 8, 9, 11, and 12, and Observation
10, that this fixes the folding sequence. Assume that
$\left|\mathcal{S}\right|\neq\left|S\right|$ and there is a fold in
$\mathcal{S}$ which splits another segment, aligns them, or leads to a
crossing. By the way we picked $\mathcal{S}$ none of these three cases can
occur when we fold the $n$ variable gadgets $S(x_{1}),\dots,S(x_{n})$. Hence,
the fold splitting, aligning, or crossing two segments must happen when the
clause gadgets are folded, but then, with Lemma 11, this can only happen in a
clause $c_{j}$, for which none of the corresponding literal segments
$S(z_{i,j})$ was in the good zone of $S(c_{j})$. However, since $\mathcal{F}$
is satisfying, this cannot be the case by Lemma 14. ∎

###  3.7 Modifying the construction

We showed that deciding if there is a solution to the restricted segment
folding problem for an instance $S$ with at most $|S|$ folds is NP-hard.
Recall that in this setting we do not allow folds along stabbing segments or
folds that produce crossings. The reduction presented above uses perpendicular
directions and constructs an instance that is not in general position, so we
cannot directly remove the folding restrictions.

If we look at the coordinates of the endpoints of $|S|$ segments in
$\mathbb{R}^{4|S|}$, the points corresponding to configurations that are not
in general position form a set of measure zero. Thus, small random
perturbations would _almost surely_ ensure that a modified instance is in
general position (even after any $|S|$ folds). We next show how to
deterministically perturb an instance $S$ produced by the reduction presented
above so that a folding sequence of length $|S|$ solving the segment folding
problem does never fold along stabbing segments or make folds that produce
crossings.

We perturb the directions of all the segments in the construction by a very
small amount that does not change the desired behaviour of the reduction but
prevents that two or more segments are folded simultaneously in an optimal
solution. We encode the segments as a tuple consisting of an endpoint, the
length, and an angle. Setting $w_{g}=400$ in the above reduction produces a
set of segments whose endpoints have integer coordinates. Thus, to encode an
endpoint and the length we can use the values of the construction, with one
exception: the only segments that are not aligned in the vertical or in the
horizontal directions are the $c^{1}$ segments in the clause gadgets. To
encode them we use the (scaled) integer coordinates of their rightmost
endpoint and set the length to $2w_{g}=800$ (instead of
$\frac{3}{2}\sqrt{2}w_{g}$). This change does not affect the behaviour of the
clause gadget.

For the angles, we include small perturbations in the following manner. We use
$O(1)+(|S|+1)^{2}$ bits (we use a binary encoding of the angles, thus showing
weakly NP-hardness). The most significant bits encode the direction defined in
the construction above, that is, one of the eight possible angles. The
remaining $(|S|+1)^{2}$ bits encode the small perturbations. We divide the
$(|S|+1)^{2}$ bits into $|S|$ groups of $|S|+1$ consecutive bits each and
assign a group to each segment. For a segment, the perturbation of the angle
consists of setting the rightmost bit of its group to $1$ (and the remaining
$(|S|+1)^{2}-1$ bits are set to $0$). When folding along a segment $s$, all
reflected segments keep their perturbation bits intact, except that in the
group corresponding to $s$ they get new bits (it gets summed the bits in that
region for $s$ shifted one position to the left). Note that by folding $|S|$
times the leading $1$ bit in a group can move at most $|S|$ positions to the
left and thus it cannot overflow into another group. In particular, this
implies that two segments cannot be aligned unless both of them (or parts of
them) have been folded before. Thus, if there is a folding sequence of length
$|S|$ it must fold each segment exactly once. This completes the modification
of the reduction and the proof of Theorem 1.

##  4 Conclusions

We have proved that given a set of segments finding the sequence minimizing
the number of folds that solves the segment folding problem is weakly NP-hard.
We also showed that the restricted segment folding problem, in which only
folds along lines that do not intersect the interior of segments and do not
produce crossings are allowed, is strongly NP-hard. Though optimizing the
number of folds in these problems is hard, it might be possible that all
instances of the segment folding problem can be solved in a polynomial number
of folds in the number of segments. In Figure 1 we presented an instance in
which an infinite sequence of folds is possible, but the shortest sequence of
folds is finite. It is an interesting open problem to find upper bounds on the
length of the shortest sequence of folds in terms of the number of segments in
the instance, or to show that this number cannot be bounded.

We conjecture that the segment folding problem is strongly NP-hard. To prove
this using our reduction we would need a deterministic perturbation of any
instance $S$ that admits a polynomial encoding in unary. We note that the
vertical separation between gadgets can be increased without altering the
correctness proof of the reduction. However, the horizontal distances are more
delicate, since we need to carefully land in the good and bad zones of clause
gadgets. For that we use a precise reset of each variable gadget. Thus, to
keep the coordinates small, instead of relying on a deterministic perturbation
the endpoints of the segments, we could make copies of all the segments. One
perturbation that we can deterministically do without blowing the coordinate
sizes more than a polynomial in $|S|$, is to alter the length of all the
segments so that no two of them have the same length. Then a possible strategy
would be to make copies of each segment in $S$ close to it but slightly
tilted, so that folding along a segment stabbing a segment in $S$ and its
copies produces too many non-perpendicular crossings.

Finally, the segment folding problem admits a natural generalization in which
folds along arbitrary lines are allowed:

Generalized Segment Folding Problem Input: A set $S$ of line segments
$s_{1},s_{2},\ldots,s_{|S|}$ in the plane and an integer $\kappa$. Operation:
Fold along any line. Question: Is there a sequence of $\kappa$ operations such
that all (parts of) segments $s_{i}$ become folding lines?

The computational complexity of this problem as well as bounds on the number
of folds needed to solve any instance are other interesting open questions.

## References

  * [1] Hugo A. Akitaya, Erik D. Demaine, and Jason S. Ku.  Simple folding is really hard.  Journal of Information Processing, 25:580–589, 2017.
  * [2] Alan Arroyo, Fabian Klute, Irene Parada, Raimund Seidel, Birgit Vogtenhuber, and Tilo Wiedera.  Inserting one edge into a simple drawing is hard.  In Isolde Adler and Haiko Müller, editors, Proceedings of the 46th International Workshop on Graph-Theoretic Concepts in Computer Science (WG’20), volume 12301 of LNCS, pages 325–338. Springer, 2020\.  doi:10.1007/978-3-030-60440-0_26.
  * [3] Devin Balkcom.  Origami robot folding a paper hat.  https://www.youtube.com/watch?v=djPdzCj4k14, 2004.  Accessed: 2019-06-19.
  * [4] Brian Chan.  The making of mens et manus (in origami), vol. 1.  http://techtv.mit.edu/collections/chosetec/videos/361-the-making-of-mens-et-manus-in-origami-vol-1, 2007\.  Accessed: 2019-06-19.