0

We continue from Cutting convex regions into equal diameter and equal least width pieces. There we had asked for algorithms to partition a planar convex polygon into (1) $n$ convex pieces of equal width with the common width maximized and (2) $n$ pieces of equal diameter with the common diameter maximized. Neither question has received a definitive answer.

Question: Given any planar convex $C$ and any $n$, if both above questions have somehow been solved (ie we have partitions of $C$ into $n$ convex pieces such that (1) the common width is maximized and (2) common diameter is minimized), will we always have a partition that answers one requirement also satisfying the other requirement? I can't find a counter example.

And let me add a weaker variant of the question: for any $C$ and $n$, will there always be some partition of $C$ into $n$ convex pieces that achieves both requirements?

Note: work by Karasev and other experts on 'fair partitions' yields a corollary that for n a prime power, partitions of any C into n convex pieces that have equal diameter and width are guaranteed; things appear open for other values of n. So, answer to even the 'weaker variant' might be unknown.

Nandakumar R
  • 5,473
  • I find extremely unlikely that the two problems you state should have the same optimal partition for general convex sets and general number of parts. I guess that "roughly speaking" for large $n$ the optimal partition will consist of patches of regular hexagons in both cases. However, it is likely that there exist perturbations of the shape $C$ which do not modify the width or diameter of one cell near the boundary while modifying the other one, contradicting simultaneous optimality. – Beni Bogosel Jan 08 '24 at 09:52
  • Thank you. In view of your comment, just added a bit to the question. – Nandakumar R Jan 08 '24 at 11:39
  • I don't think the modification of the question adds something new... There is no reason to assume that the two partitions are the same for every convex C. – Beni Bogosel Jan 08 '24 at 11:48
  • I meant: "for a C, there could be a set of n-partitions that maximize an equal width among pieces and another set of n-partitions that achieve min of equal diameter; will these two sets of partitions always have some intersection?" – Nandakumar R Jan 08 '24 at 12:13
  • It would help me gain some more clarity if you could show a specific example for some C and some small n wherein the two requirements can be met by different n-partitions of C. – Nandakumar R Jan 08 '24 at 12:15

0 Answers0