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



Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.