Assume you have a 2-dimensional pizza with $2n$ ingredients that you want to share with your friend. For this you are allowed to cut the pizza using several straight cuts, and then give every second piece to your friend. You want to do this fairly, t
hat is, your friend and you should each get exactly half of each ingredient. How many cuts do you need? It was recently shown using topological methods that $n$ cuts always suffice. In this work, we study the computational complexity of finding such $n$ cuts. Our main result is that this problem is PPA-complete when the ingredients are represented as point sets. For this, we give a new proof that for point sets $n$ cuts suffice, which does not use any topological methods. We further prove several hardness results as well as a higher-dimensional variant for the case where the ingredients are well-separated.
Assume you have a pizza consisting of four ingredients (e.g., bread, tomatoes, cheese and olives) that you want to share with your friend. You want to do this fairly, meaning that you and your friend should get the same amount of each ingredient. How
many times do you need to cut the pizza so that this is possible? We will show that two straight cuts always suffice. More formally, we will show the following extension of the well-known Ham-sandwich theorem: Given four mass distributions in the plane, they can be simultaneously bisected with two lines. That is, there exist two oriented lines with the following property: let $R^+_1$ be the region of the plane that lies to the positive side of both lines and let $R^+_2$ be the region of the plane that lies to the negative side of both lines. Then $R^+=R^+_1cup R^+_2$ contains exactly half of each mass distribution.
