Cake cutting part 3
Home Blog About Us Work we do Content Contact Us
 

Newsletter: Click here to join an email list and be contacted when a new article is published.

 

 

 Advertisement 

Cake cutting part 3

This article builds on two previous articles about cutting a circular cake into eight equal sized pieces.

(If needed, you can read those earlier articles here and here for background).

There are ways to do better in some of the families of solutions I gave in the previous articles; solutions can be found that reduce the total length of the cut needed, though they add additional criteria, such as requiring cuts that do not go edge-edge, or increase the number of discrete cuts needed.

It's clear that I poorly defined the problem. I'll attempt to redress that with this article.

If we wanted to cut a cake into eight pieces of equal size (not shape), what is the shortest overall length of cut needed? We'll group families of solutions based on the number of discrete straight cuts used. We're not allowed to restack pieces after any cut, and cuts do not have to go from edge to edge.

All cuts have to be orthoganol to the surface of the cake (meaning this is really a problem of how to carve up a circle into eight regions of equal area).

Below are what I think are the optimal solutions. If you can do better, please let me know, and I'll continue to update!

We're assuming a normalized circle with unit radius, so all lengths are quoted based on this.

Four Cuts

Becuase we're not able to restack the pieces, the minimum number of cuts is four. The traditional sector cut requires 8 units, and by using the technique calculated in the first article, we can reduce this down to 7.66 units (show below right).

The solution on the right also has the bonus that cuts are still made edge-to-edge. This was the results I showed in my first article that started all this follow-up! (I poorly stated the problem).

Six Cuts

We'll look at six cuts as way to get to five cuts.

If cuts don't need to need to go edge-edge, then we can do better by angling the two outer lines slightly. Even though this results in a slightly longer cut, because of the circular cake, it allows more region on one side, and can be compensated by sliding the intersection point closer to the middle. There is an optimal angle, and this was covered in the Second article.

Even though these cuts are not all edge-edge, each of the cuts does, at least, have one vertex on the edge of the cake. This allows a cake carver to start each cut from the edge of the cake. No plunge cuts are needed! (This means that if you need to cut Grandama's special fruit cake, you can still use a band saw with no problem).

Five Cuts

We can make the total length of cuts needed shorter, and use one fewer cuts if we are allowed plunge cuts (cuts that do not start at any edge). This is something I overlooked on my first analysis. It's an interesting diversion.

Rather than making the vertical bisecting cut (which would be two units long down the center), it's more efficient to bisect each of the halves by a cut in the orthoganol direction).

This simple optimisation reduces the total legth down to ≈ 7.27 units. (Below are the details)

So if this technique works to reduce the length of the straight line solution above, it could also be applied to reduce the sloped solution below shown below right? Yes? Hold on, not so fast, we'll need to check this out. Because of the slope, the closer to the edge this cross-bar goes, the wider it becomes (in the solution above, as the uprights are parallel, it does not matter where they go).

We'll need to do some calculations:

We need to calculate b and h that enables a trapezium of one eighth of the area of the circle. We already know the slope of the cuts, so that angle can be determined.

A little bit of algebra gives the result of b ≈ 0.868, and h ≈ 0.550

This gives the total length of cuts at ≈ 7.25, which is close to the value we obtained from the straight-upright cut optimisation.

Below, to a higher precission, are the total lengths of the cuts using the various methods.

SolutionCut Length% improvment
Sector cut 8.00000 -
Straight uprights 7.65908 4.2615%
Angled uprights 7.50975 6.1281%
Straight uprights and horizontal crossbar 7.27497 9.0629%
Angled uprights and horizontal crossbar 7.24592 9.4260%

Fourteen cuts

If we graduate to fourteen cuts, as discussed in the last article, we can carve the cake into eight pieces by cutting a regular heptagon in the center and seven radial arms from the vetices.

Through symmetry, all the seven pieces around the annulus are the same shape, and make up of 7/8ths of the area of the circle. The regular heptagon in the center is made of 1/8th of the area.

SolutionCut Length% improvment
Sector cut 8.00000 -
Straight uprights 7.65908 4.2615%
Angled uprights 7.50975 6.1281%
Straight uprights and horizontal crossbar 7.27497 9.0629%
Angled uprights and horizontal crossbar 7.24592 9.4260%
Heptagon center 6.64935 16.883%

That's quite an improvement!

The side of the heptagon is ≈ 0.328733, and the vertices are at a radius of ≈ 0.378826 (see previous article for details).

More Cuts …

The total length of cake cut has two components; the radial spurs, and the sides of the heptagon. If we moved the vertices out a little, we could reduce the length of all of the outside cuts. A consequence of this is that the area of the center heptagon would be increased, and that of segments on the outside would decrease.

We can compensate for this by adding an additional vertex in the middle of each of the sides of the heptagon, and pushing this into the heptagon to make it star shape. This will reduce the area of the center piece.

As long as the additional length added to the sides by 'buckling' of the edges of the heptagon is less than the length reduced be moving out the vertices, it will increase the efficiency of the solution.

There are 14 similar triangular pieces in the star. Each has an angle Φ = 360°/14 ≈ 25.71°

The formula for the area of each triangle is given below. We know the area we need to make each triangle, and we know the angle. So, if we know r1, then we can calculate the value that r2 will need to be to preserve the area.

Finally, using the cosine rule, we can determine the length of edge of the star.

Below is a table generated by displacing the vertices of the heptagon an increasing distance radially outwards. You can see that, initially, as they are displaced outwards, even with buckling the sides and increasing the length (to preserve the area of the center piece), the overall length of cuts decreases. However, a maximum is soon obtained, and further increasing the radius increases the total cut length again.

In the table below, the delta column is the amount (in units) that that each of the vertices is displaced outwards (radially). r1 is the value of this radius of this vertex, and r2 is the value that the midpoint vertex needs to be to preserve the area. Edge is the length of the outside edge of the triangle (t) and the total column measures the entire lengths of all the cuts needed. As before, the percentage column shows the improvement over the basic sector cut.

deltar1r2EdgeTotal CutPercent
0.0000000.3788260.3413100.1643666.64934816.8831%
0.0002000.3790260.3411300.1644546.64916916.8854%
0.0004000.3792260.3409500.1645426.64900016.8875%
0.0006000.3794260.3407700.1646306.64884216.8895%
0.0008000.3796260.3405900.1647206.64869616.8913%
0.0010000.3798260.3404110.1648106.64856016.8930%
0.0012000.3800260.3402320.1649016.64843516.8946%
0.0014000.3802260.3400530.1649936.64832116.8960%
0.0016000.3804260.3398740.1650866.64821816.8973%
0.0018000.3806260.3396960.1651796.64812616.8984%
0.0020000.3808260.3395170.1652736.64804416.8994%
0.0022000.3810260.3393390.1653686.64797416.9003%
0.0024000.3812260.3391610.1654646.64791316.9011%
0.0026000.3814260.3389830.1655606.64786416.9017%
0.0028000.3816260.3388060.1656586.64782516.9022%
0.0030000.3818260.3386280.1657566.64779616.9025%
0.0032000.3820260.3384510.1658546.64777816.9028%
0.0034000.3822260.3382740.1659546.64777116.9029%
0.0036000.3824260.3380970.1660546.64777416.9028%
0.0038000.3826260.3379200.1661556.64778816.9027%
0.0040000.3828260.3377440.1662576.64781216.9024%
0.0042000.3830260.3375670.1663596.64784616.9019%
0.0044000.3832260.3373910.1664626.64789016.9014%
0.0046000.3834260.3372150.1665666.64794516.9007%
0.0048000.3836260.3370390.1666716.64801016.8999%
0.0050000.3838260.3368640.1667766.64808616.8989%

A maximum of ≈ 16.9029% improvement can be obtained by the addition of an additional vertex at the midpoint of each side. A graph of this data is show below. It's a small change (less than 1% increase in the length of r1).

This small improvement came about through the additional of just a single mid-point vertex in the edge of the heptagon. If we placed additional vertices in the edges we could make incrementally smaller and smaller improvements as the edge of the heptgaon transformed from having straight sides to gently bowed curves. (It would actually be a fun exercise to attempt to model this as a series of springs to see the shape of the curve, holding in 'pressure' of the areas they contained).

Closer to the Steiner Tree

In the basic heptagon solution, the angles at the triple points are shown below on the left. The internal angle of the heptagon is ≈ 128.57° With the addition of the mid-point vertices, the internal angle relaxes to ≈ 124.36°

As additional vertices are added, forming the curve as described above, the internal angles will get closer and closer to the 120° angles predicted by Steiner trees.

 

You can find a complete list of all the articles here.      Click here to receive email alerts on new articles.

© 2009-2017 DataGenetics    Privacy Policy