# Fair division of an octagon

A land-plot belongs to two partners. Its form is a regular octagon with area 1.

They want to divide it such that one gets area $p$ and one gets area $1-p$, where $p \in (0,1)$ is a given constant.

One way to do it is just to continuously move a straight line over the octagon, say, from east to west. The area to the east of the line grows continuously from 0 to 1, therefore by the intermediate value theorem it must cross $p$ at some point.

The problem with this division is that one of the plots might be too narrow, and unuseful. So the partners agree on the following condition:

Each land-plot should be convex and contain a square with an area of at least half the area of the land-plot.

I.e., one partner should get a square with area at least $p \over 2$, and the other should get a square with area at least $(1-p) \over 2$.

Is this possible for all $p$?

If the answer is no - does it become possible if we allow the land-plots to be non-convex?

-

# No convex solution

## With intuition

If both areas are to be convex, then the curve dividing them must be a straight line. A straight line cutting into the octagon parallel to one of its edges is bad, since it results in one very narrow plot for small $p$. So intuition tells me that a line whose direction is exactly between two adjacent edges should be best, in terms of area of a square versus whole area of the plot. The situation for small $p$ then looks as follows:

In this case, the area of the square, in relation to the whole yellow area, is

$$\frac{4 \, \sqrt{\sqrt{2} + 2} {\left(\sqrt{2} - 2\right)}}{4 \, \sqrt{\sqrt{2} + 2} {\left(\sqrt{2} - 2\right)} - {\left(3 \, \sqrt{2} + 10\right)} \sqrt{-\sqrt{2} + 2}} \approx 0.28427 < \frac12$$

So no, there is no convex solution.

## Bounds without intuition

You might not trust my intuition. You might also be worried about how to orient the square. But perhaps the following plot can convince you:

The horizontal axis of that plot shows the angle under which your line intersects the octagon, measured in degrees. In the center there is the middle solution depicted above, while those position where the function value is zero correspond to a line parallel to one of the edges.

What the vertical axis plots is the area of a square, divided by the area of the whole plot. That square is not neccessarily contained in the plot; instead it is the square circumscribed around the incircle of the triangular plot. Every square has an incircle, and the larger the incircle, the larger the square. So the largest square which fits into the plot has to have an incircle no larger than that of the plot itself. Therefore the value plotted is an upper bound for the value of the ratio you would obtain for the largest fitting square. You will see that it still falls well short of $\frac12$. In fact, its optimal value is for the situation discussed above, and in that case the bound estimated by this incircle argument is still only

$$44 \, \sqrt{2} - 8 \, \sqrt{82 \, \sqrt{2} + 116} + 60\approx0.382\lt0.5$$

# Non-convex solution

does it become possible if we allow the land-plots to be non-convex?

Yes it does. You can sweep through the octagon the way you describe it, but have a square of area $\frac p2$ protrude into the other area. The sweeping line would then be chosen such that it covers $\frac p2$ of the area of the octagon minus the square. Here is an illustration of typical situations which could occur during such a sweep. The squares are always as large as the associated non-square regions of the similar color, so they are half as large as the whole plot obtained in this fashion.

Now you can look at the positions of the contained squares, depending on the parameter $p$:

The red line is the position of the divider line. The orange and green line pairs denote the positions of the squares. As you can see, these never overlap, so there is never a problem of the squares intersecting. And the red divider line only divides the remainder after the squares were already taken away, so it won't conflict with anything either.

## Events where things change

The blue dots denote special situations, from left to right:

1. The red line touches the left pair of corners of the octagon
2. The yellow area fully encloses the orange square
3. The orange square no longer touches the left edge
4. The green square begins to touch the right edge
5. The green square protrudes beyond the cyan area
6. The green red line touches the right pair of corners of the octagon

The situations depicted above illustrate arrangements between these special situations, but only for the first half of the spectrum.

The relevant $p$ values where these events occur are

\begin{align*} p_1&= -\frac{1}{8} \, \sqrt{2} {\left(\sqrt{2} \sqrt{2 \, \sqrt{2} - 1} - \sqrt{2} - 2\right)} \approx 0.2655 \\ p_2&= \frac{1}{16} \, \sqrt{2} {\left(\sqrt{2} \sqrt{2 \, \sqrt{2} - 1} + 3 \, \sqrt{2} - 2\right)} \approx 0.3672 \\ p_3&= \frac{1}{\sqrt{2} + 1} \approx 0.4142 \\ p_4&= \frac{\sqrt{2}}{\sqrt{2} + 1} \approx 0.5858 \\ p_5&= -\frac{1}{16} \, \sqrt{2} {\left(\sqrt{2} \sqrt{2 \, \sqrt{2} - 1} - 5 \, \sqrt{2} - 2\right)} \approx 0.6328 \\ p_6&= \frac{1}{8} \, \sqrt{2} {\left(\sqrt{2} \sqrt{2 \, \sqrt{2} - 1} + 3 \, \sqrt{2} - 2\right)} \approx 0.7345 \end{align*}

I have symbolic formulas which compute the sweep line position and so on, one formula for each piece delimited by such events. But some formulas are pretty big, so I won't paste them here.

-
Wow, thanks for the amazing answer. Can you please explain how you calcualated "the square circumscribed around the incircle of the triangular plot"? –  Erel Segal-Halevi Nov 21 '13 at 18:50
@Erel: I assumed the octagon corner in the origin, and the two other plot corners at $(\tan(\varphi-\frac38\pi),1)$ and $(\tan(\varphi+\frac38\pi),1)$. From this I computed triangle lengths, and using this formula I computed the inradius $r$. Then the area of the circumscribed square is simply $4r^2$. Here is a plot of the resulting function, including the formula I obtained. –  MvG Nov 21 '13 at 20:41