0
$\begingroup$

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.

Improve this question
$\endgroup$
5
  • $\begingroup$ 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. $\endgroup$
    – Beni Bogosel
    Commented Jan 8 at 9:52
  • $\begingroup$ Thank you. In view of your comment, just added a bit to the question. $\endgroup$
    – Nandakumar R
    Commented Jan 8 at 11:39
  • $\begingroup$ 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. $\endgroup$
    – Beni Bogosel
    Commented Jan 8 at 11:48
  • $\begingroup$ 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?" $\endgroup$
    – Nandakumar R
    Commented Jan 8 at 12:13
  • $\begingroup$ 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. $\endgroup$
    – Nandakumar R
    Commented Jan 8 at 12:15

0

Reset to default

You must log in to answer this question.