6
$\begingroup$

Let $K$ be a compact convex set in the plane.

Say that a perimeter-halving partition of $K$ is a partition of $K$ into two pieces by a chord (a segment with endpoints on the boundary $\partial K$) each of which includes half of the perimeter of $K$. For conciseness, call a perimeter-halving partition an equipartition.

I am interested in equipartitions that leave the areas of the two pieces unbalanced: equal icing but unequal cake in the cake-cutting analogy. For example, partitioning an equilateral triangle with an altitude is an equipartition but also partitions the area into equal halves. Here is an equipartition that leads to one piece with about 56% of the area and the other 44% (if I've calculated correctly):


          UnbalancedEquipartition
For a given $K$, finding the most unbalanced equipartition seems like an interesting algorithmic challenge. But my questions are a bit different:

Q1. Which shapes $K_{\mathrm{ext}}$ permit the most extreme unbalanced partition, in that the area ratio of the two halves is maximized over all shapes?

Perhaps $K_{\mathrm{ext}}$ is degenerate, only achieved in the limit?

Now consider repeated equipartitions. Suppose your goal is to end up with the largest area piece after $n$ equipartitions starting from a given $K=K_0$. A natural strategy is to use the most unbalanced equipartition on $K_0$, and to let $K_1$ be the larger-area half of that 1st equipartition. Then use the most unbalanced equipartition on $K_1$, and to let $K_2$ be the larger-area half of that 2nd equipartition. And so on, always at each step using the most unbalanced equipartition and selecting the larger-area half for the next step, ultimately leading to $K_n$.

Q2. Is that strategy optimal, or might it sometimes be better (resulting in a larger area $K_n$) to not use the most unbalanced equipartition at some step, or to select the smaller-area half for the next step?

One can ask similar questions reversing the roles of perimeter and area. And the questions may be generalized to $\mathbb{R}^d$.


Addendum. To answer a question in a now-deleted comment, the context here is that any perimeter-halving of a convex polygon results in a convex polyhedron when the two perimeter halves are identified (glued together). For example, here is the polyhedron that results from a particular perimeter-halving of a regular duodecagon:
      Pita25.40
This is Fig.25.40 (p.413) in Geometric Folding Algorithms. More generally, a perimeter-halving folding of a convex shape $K$ results in a convex body in $\mathbb{R}^3$. I was seeking to understand how different can be the "top" and "bottom" of the folded shape. The repeated-equipartitions question was primarily curiosity in the same intellectual vicinity.

$\endgroup$
3
  • 5
    $\begingroup$ Q1 is easy: take an almost degenerate obtuse triangle and cut along the longest side (the base). You need to take off just a tiny portion of the lateral sides to achieve the balance of the perimeter, which means that the bottom piece has no noticeable area compared to the whole. $\endgroup$
    – fedja
    Dec 17, 2014 at 14:39
  • 3
    $\begingroup$ For Q2 here is an idea. If you start with a square, all choices at the first step are equally good, but the result of the second step does depend on the shape. Now, take a suboptimal first step and perturb the square just slightly to make it the choice in your algorithm (what is not so obvious to me off hand is whether this is possible, so it is an idea, not a proof, at this moment but, I guess, we can figure out in finite time if it works as is or with a slight modification). $\endgroup$
    – fedja
    Dec 17, 2014 at 14:46
  • $\begingroup$ @fedja: I find your idea insightful and almost certainly correct. I love your "finite time" remark :-), but so far I have not found more than $\epsilon$ of time to pursue it... $\endgroup$ Dec 19, 2014 at 23:06

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.