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).
