Skip to main content
correction in the title
Link
Nandakumar R
  • 6k
  • 3
  • 7
  • 20

Comparing partitions of a given planar convex region into pieces with equal perimeterdiameter and pieces of equal width

added 356 characters in body
Source Link
Nandakumar R
  • 6k
  • 3
  • 7
  • 20

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.

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.

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?

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.

added 39 characters in body
Source Link
Nandakumar R
  • 6k
  • 3
  • 7
  • 20

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.

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 the samea partition answering both requirementsthat 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?

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.

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 the same partition answering both requirements? I can't find a counter example.

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

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.

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?

added 169 characters in body
Source Link
Nandakumar R
  • 6k
  • 3
  • 7
  • 20
Loading
Source Link
Nandakumar R
  • 6k
  • 3
  • 7
  • 20
Loading