# Complexity of best folding of a 2D set (or how to optimize a sandwich)

Motivation: I was making lunch for my son, part of which is making a sandwich from two halves of a slice of bread. In order to minimize the parts of bread that have cheese on them, and are not covered by both halves, I need to find the optimal place to cut the bread.

I was wondering what the complexity of that is.

Formal problem: Let $$S\subseteq \mathbb{R}^2$$ be either a polytope, or more generally a semialgebraic set. For a line $$\ell\in \mathbb{R}^2$$, given by its normal $$w\in \mathbb{R}^2$$, we define the cut of $$S$$ by $$\ell$$ to be the two sets: $$S_1=\{x\in S\ :\ x^Tw\ge 0\}\qquad S_2=\{x\in S\ :\ x^Tw< 0\}$$ Now, given an affine linear isometry $$f(x)=Ax+b$$, we can consider the area of $$\Delta(S_1,f(S_2))$$. That is, the area of the symmetric difference between $$S_1$$ and the isometry applied to $$S_2$$.

The problem is now the following:

Given $$S\subseteq \mathbb{R}^2$$, find a line $$\ell$$ and an affine isometry $$f$$ such that $$\Delta(S_1,f(S_2))$$ is minimal.

If it helps, we can assume $$S$$ is convex (although homemade bread often isn't).