Puzzle
a.
Let F(N) denote the worst (greatest) possible ratio of splitline-length
to optimum cut-length.
We know from
Baumann's conjectured optimal configurations for N=1,2,3,4,5,6 when the rectangle
is a square (see also our
puzzle 66)
that
In the limit N→∞ we shall now demonstrate that limsup F(N)≥(3^{1/2}+3^{-1/2})/12^{1/4}≈1.24086. To see this, consider a square being divided into N=3·4^{k} pieces. The result with shortest splitline algorithm is a grid consisting of identical rectangles each with the proportions 3×1. The half-perimeter of such a rectangle with unit area is 3^{1/2}+3^{-1/2}. Meanwhile the optimum partitioning is known by a result of Thomas C. Hales to be asymptotically the same length as the regular-hexagon "honeycomb," and note a unit-area regular hexagon has half-perimeter 12^{1/4}. (We did not actually need Hales's result, we merely need the trivially easier result that the honeycomb upper bounds the optimum.) Q.E.D.
We can also show liminf F(N)≥2/12^{1/4}≈1.0745699 by noting that no matter what N is (power of 2, or not) the final rectangles will always have perimeter at least as large as a square with the same area. (Which follows from the fact L+W is minimized with LW=1 and L,W>0 when L=W=1.)
In the same limit we now shall demonstrate the matching upper bound limsup F(N)≤(3^{1/2}+3^{-1/2})/12^{1/4}≈1.24081, thus demonstrating equality – we know the limsup's exact value. This will solve problem e. Suppose we have an A×B rectangle, A≥B. (We say its "aspect ratio" is A/B.) The shortest splitline will have length B and the new two rectangles will each have aspect ratios 2B/A if N is even and if 2B>A. Even in the worst case where N=3, the aspect ratios will be 3B/A and 3B/(2A). The point of this is that
In view of the second and third points, the final splitline districting will consist entirely of equal-area rectangles, all with aspect ratio≤3, in the N→∞ limit; this in combination with Hales's honeycomb-optimality theorem implies our upper bound.
I conjecture this limit-constant 1.2408 works not only for rectangular countries but in fact for every convex country-shape. (The intuition behind the conjecture is that in the N→∞ limit, splitlined districts will almost all be almost-rectangular.)
b. A country consisting of three equal-area blobs joined by a "Y" of thin filaments, is a counterexample. Another is:
The country (shaped like two rectangles of slightly-unequal size joined by a short thin neck) can be divided in half by either (A) a short circular arc, or (B) a much longer line segment.
c. A square country with a high-population-density city near the midpoint of its East edge, and low-density rural everywhere else (total rural≈total urban population), is a counterexample with N=2. A tiny semicircle chopping off the city (or a tiny circle, if the city instead is located internally) has far smaller cutlength than the shortest splitline.
d. Splitlines are all-internal for a convex country by the definition of convexity and the inductive production of convex hemi-countries in all such splits.
f. Define the "aspect ratio" of a convex plane region R to be its diameter D (furthest point-pair separation) divided by its width W (minimum separation between two parallel lines enclosing R). The shortest splitline for any given population ratio always has length≤W. It is not hard to see that once our convex region has aspect ratio≤C, for some appropriate constant C depending roughly linearly on the ratio of upper to lower bounds for the allowed-population-density window, then it will never rise above C no matter how much further splitting is done to it. This aspect ratio bound in turn may be used to see that the Approximation Conjecture is true (again for some ratio-constant) in the N→∞ limit.
Other remarks. Raphfrk points out this lower bound
One can argue that the shortest curve-length L cutting a convex area=A width=W body into two parts while exactly bisecting area, obeys
For an equilateral triangle with SideLength=1, Baumann's optimal cut (via an arc) into two pieces has cut length √(3π√3)/6≈ 0.6733868440 whereas the shortest splitline algorithm produces a cut-line with length 1/√2≈0.7071067812 for an approximation ratio of about 1.050075. One perhaps could prove the N=2 uniform case has this approximation ratio in the worst case?
For an equilateral triangle with SideLength=1, the optimal cut (via three line segments) into three pieces has cut length (√3)/2≈0.8660254040 whereas the shortest splitline algorithm produces cut-length (5√3 - 3)/6≈0.9433756730, for an approximation ratio of about 1.089316. Perhaps this too is the worst possible ratio when N=3?
The shortest splitline sliceup of an equilateral triangle into N=4 equiareal pieces has length (1+√3+√2)/2 + (√6)/4 ≈ 1.460759749 as opposed to the conjectured minimal-length splitup (by J.Hall & E.Baumann) with cut-length≈1.305113032, for ratio≈1.119259185. [This is the greatest ratio I currently know for any convex shape with N≤6.]
A.Heppes remarked the following. If you decompose the surface of a sphere into N equal-area regions for any N>0 with N≠{2,3,4,6,12}, then the shortest net that does the job necessarily contains a nonconvex cell (because it will have a circular arc as part of its boundary).