Tag: geometry

Deriving formulas for the areas

Let’s start by assuming the pizza is a circle of radius 1, and let’s use a coordinate system where the origin is at the center of the pizza. Since all cuts must intersect at a common point on the inside of the circle, we can rotate the circle such that the intersection point lies on the positive $x$-axis. Let the intersection point be $X$ and have coordinates $(x,0)$. We make $n$ cuts through this point, which will result in $n$ chords that intersect the circle at $n$ points above the $x$-axis and $n$ points below, so $2n$ total points.

• Let $\theta_i$ denote the angle that point $i$ makes with the positive $x$-axis, measured with respect to the intersection point $X$.
• Let $\phi_i$ denote the angle that point $i$ makes with the positive $x$-axis, measured with respect to the origin $O$.
• Let $L_i$ denote the length of the line segment between point $i$ and the intersection point $X$.

The figure below illustrates one possible set of cuts for the case $n=3$.

Now we must compute the areas of the different slices. One such slice, between cuts $1$ and $2$, is shaded in the diagram above. We will split each slice into its triangular part $\triangle_{12}$ and its rounded part $\bigcirc_{12}$.

• The triangular part is the triangle $XP_1P_2$. Based on the side lengths $XP_1=L_1$ and $XP_2=L_2$ and angle $\angle P_1XP_2=\theta_2-\theta_1$, the area is
  \[
  \triangle_{12} = \frac{1}{2}L_1L_2 \sin(\theta_2-\theta_1)
  \]

• The rounded part is the difference between the circular sector $O P_1P_2$ and the triangle $OP_1P_2$. Since the pizza has radius $1$, $OP_1=OP_2=1$. The circular sector has area $\frac{1}{2}(\phi_2-\phi_1)$ and the triangle has area $\frac{1}{2}\sin(\phi_2-\phi_1)$. Therefore, the slice between cuts $1$ and $2$ has total area:
  \[
  \bigcirc_{12} = \frac{1}{2}\left( (\phi_2-\phi_1)-\sin(\phi_2-\phi_1)\right)
  \]

Our next task will be to express $\phi_i$ and $L_i$ in terms of $x$ and $\theta_i$. Consider the point $P_i$. We can write its coordinates in two different ways depending on whether we arrive there via $O\to P_i$ or $O\to X\to P_i$. This yields
\[
P_i = \begin{bmatrix}\cos\phi_i \\ \sin\phi_i\end{bmatrix}
= \begin{bmatrix}x + L_i \cos\theta_i \\ L_i\sin\theta_i \end{bmatrix}
\]squaring these equations and summing them to eliminate $\phi_i$, we obtain
\[
1 = (x+L_i\cos\theta_i)^2+L_i^2\sin^2\theta_i
\]Solving for $L_i$ and keeping the positive root (since $L_i \gt 0$), we find
\[
L_i = \sqrt{1-x^2\sin^2\theta_i}-x\cos\theta_i.
\]Putting everything together, we now have a formula for the area of a slice! In the case of the slice between cuts $1$ and $2$, the area would be:

$\displaystyle
\begin{aligned}
A_{12}(x,\theta_1,\theta_2) &= \frac{1}{2}L_1L_2 \sin(\theta_2-\theta_1) + \frac{1}{2}\bigl( (\phi_2-\phi_1)-\sin(\phi_2-\phi_1)\bigr) \\
\text{where:}\,\,& \left\{\begin{aligned}
L_i &= \sqrt{1-x^2\sin^2\theta_i}-x\cos\theta_i \\
\phi_i&= \arccos\left(\cos\theta_i\sqrt{1-x^2\sin^2\theta_i} + x \sin^2\theta_i \right)
\end{aligned}\right.
\end{aligned}
$

Similar formulas hold true for the remaining slices, so if we have $n$ cuts and we specify the location $x$ of the intersection and the angles $\theta_1,\dots,\theta_n$, we can find formulas for areas of each of the slices $A_{ij}$.

Finding an optimal set of cuts

If we have $n$ cuts, there will be $2n$ slices. To keep things simple, let’s normalize the areas so that the total area is $1+2+\dots+2n=2n^2+n$, and let’s label the normalized areas $A_1,\dots,A_{2n}$ (in counterclockwise order, starting from $A_{12}$). The reason for doing this is that for example in the case $n=2$, we want the $4$ slices to be in the ratio $1:2:3:4$. So we normalize the total area to be $1+2+3+4=10$. That way we can directly try to make $A_1=1$, $A_2=2$, etc.

Each area will be a function of the parameters $\{x,\theta_1,\dots,\theta_n\}$. The goal is to find the set of parameters that give areas that are as close to the numbers $1,2,\dots,2n$. There are many ways to define “closeness”. I will use the least squares criterion, which does a good job in this case because it ensures that all areas are “roughly equally close” to what they should be and there are no large deviations.

For example, in the case $n=2$, our task would be to pick $(x,\theta_1,\theta_2)$ such that the following function is minimized:
\[
J_1 = (A_1-1)^2 + (A_2-2)^2 + (A_3-3)^2 + (A_4-4)^2
\]But there is more… What if the slices do not occur in this particular order 1,2,3,4? We should also check other permutations! For example, we should also try the functions:
\begin{align}
J_2 &= (A_1-1)^2 + (A_2-2)^2 + (A_3-4)^2 + (A_4-3)^2 \\
J_3 &= (A_1-1)^2 + (A_2-3)^2 + (A_3-2)^2 + (A_4-4)^2 \\
&\cdots
\end{align}In all, there will be $(2n)!$ permutations, or $24$ in the case $n=2$. This number can be reduced by a factor of $2$ if we leverage symmetry in reflection.

So our process will be as follows:

1. pick a permutation $p$ of $\{1,2,\dots,2n\}$
2. Find $(x,\theta_1,\dots,\theta_n)$ that minimizes the least squares cost
   \[
   J_p = \sum_{i=1}^{2n} \bigl(A_i(x,\theta_1,\dots,\theta_n)-p_i\bigr)^2
   \]subject to the constraints $0\leq x\leq 1$ and $0\leq \theta_1\lt\cdots\lt\theta_n\leq \pi$.

3. If we can obtain $J_p=0$, then we have a perfect match and we can stop. Otherwise, return to step 1 and pick a different permutation $p$. Repeat until all permutations have been tested.

The function $J(x,\theta_1,\dots,\theta_n)$ is a difficult (read: nonconvex) function, but still relatively well-behaved (read: continuously differentiable), so standard off-the-shelf solvers are adequate for the task. I used Matlab’s constrained nonlinear optimizer fmincon.

The case of 4 slices

For the case $n=2$ (4 pieces), it is possible to achieve the exact desired ratio. Here is one solution that works, where I labeled each slice with its normalized area.

In the case above, $x=0.3406$, and $\theta = \{0^\circ, 69.838^\circ\}$. This case is nice because $1+4=2+3$, so one of the cuts is actually a diameter and cuts through the center! In all, there are six permutations that lead to valid solutions for the case of 4 slices:

Each solution in the left column has a “twin” next to it in the right column, which comes from reflecting the solution about the $x$-axis.

The case of 6 slices

In this case, it is not possible to achieve the exact desired ratio. Some permutations can get “closer” (in the least squares sense), so in order to find the best one, we must try all possible permutations. The smallest least squares error achievable turns out to be $0.0024$, and it is achieved by a single permutation (and its twin). Here is that solution. Again, I labeled each slice with its normalized area.

This solution corresponds to $x=0.3488$ and $\theta=\{19.200^\circ, 80.363^\circ, 160.910^\circ\}$.

The case of 8 slices

This case is similar to the previous one. This time, the smallest least squares error achievable is $0.0032$, and again it is achieved by a single permutation (and its twin). Here is that solution.

This solution corresponds to $x=0.1875$ and $\theta=\{ 13.768^\circ, 28.356^\circ, 68.600^\circ, 135.310^\circ\}$. Interestingly, even though there are permutations that would lead to an even split, such as $2+3+5+8=1+4+6+7$ (such a split would mean that one of the cuts goes through the center), none of these even splits produce a solution that comes as close to the desired ratio as the one above.