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$ Commented Jan 8, 2024 at 9:52
  • $\begingroup$ Thank you. In view of your comment, just added a bit to the question. $\endgroup$ Commented Jan 8, 2024 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$ Commented Jan 8, 2024 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$ Commented Jan 8, 2024 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$ Commented Jan 8, 2024 at 12:15

0

Reset to default

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.