2
$\begingroup$

This post is a spinoff from Cutting convex regions into equal diameter and equal least width pieces

Definitions: The diameter of a convex region is the greatest distance between any pair of points in the region. The least width of a 2D convex region can be defined as the least distance between any pair of parallel lines that touch the region.

  1. Consider dividing a 2D convex region C into n convex pieces such that the maximum diameter among the pieces is a minimum. Will such a partition necessarily require all pieces to have the same diameter? This looks unlikely but I have no counter example.

Remark: Maximizing the least diameter among n convex pieces can be seen to have no neat solution - with most of the pieces near-degenerate, one can achieve, for each piece a diameter arbitrarily close to the diameter of C itself. However, I can't think of any quantity such that if we try to minimize the maximum of this quantity among n convex pieces, we would get degenerate pieces.

  1. If the lowest least width among n convex pieces into which C is being cut ought to be maximized, will such a partition necessarily be one where all pieces have same least width? Again, one has no counter example.

Note 1: For both questions, one might have a "not true in general but true for sufficiently large and finite n" answer. But this is a guess.

Note 2: Not sure if question 2 is related to the Plank Problem. Maybe not because maximizing the lowest least width of the pieces appears to favor triangular pieces rather than planks.

Note 3: From question 2, one can derive what seems to be a bunch of related questions: Given a positive integer n, find the smallest convex region C ("smallest" could mean least area, least diameter or least perimeter) such that from C, n convex regions can be cut with the least width of each being at least equal to unity.

Further Thoughts: If maximum (minimum) area among n convex pieces is to be minimized (maximized), then, it is easy to see all pieces should have same area. Maximizing (minimizing) the minimum (maximum) perimeter among n convex pieces also probably equalizes the perimeter among pieces(I have no proof) - for the n=2, this is easily true.

Note (13th November 2021): Another quantity that can be considered for minimizing the maximum (maximizing the maximum) among n pieces is the moment of inertia.

A guess: To maximize the least perimeter among n convex pieces cut from a convex region C, at least one of the cut lines necessarily ends at an end of a diameter of C.

Improve this question
$\endgroup$
0

1 Answer 1

Reset to default
2
$\begingroup$

Not an answer, just an example for Question 1. Here is a partition of the unit square into $n=3$ incongruent quadrilaterals whose maximum diameter is a candidate for the minimum possible. Indeed all three diameters (blue) are equal, to $2 \sqrt{2 - \sqrt{3}} \approx 1.04$.

       enter image description here

I haven not proven that this is the min diameter $3$-partition. Note that the natural partitioning of the square into three $1 \times \frac{1}{3}$ rectangles leads to a larger diameter, $\frac{\sqrt{10}}{3} \approx 1.05$.

Improve this answer
$\endgroup$
7
  • 1
    $\begingroup$ As was noted in mathoverflow.net/questions/375536/…, although it is proved that partition into n convex pieces all of same diameter exists for any convex C, the proof technique does not aim to actually find such a partition. To find any such partition seems a tough algorithmic challenge. Indeed, cutting a square into 3 pieces itself has now given a surprise (that the natural partition into 3 identical rectangles is not the partition with least max diameter among pieces - and that too by the smallest of margins! $\endgroup$
    – Nandakumar R
    Dec 9, 2020 at 7:08
  • 1
    $\begingroup$ Somewhat related: the "three cowboys" problem in Steinhaus, One Hundred Problems in Elementary Mathematics. $\endgroup$
    – Gerry Myerson
    Feb 21, 2021 at 22:33
  • 2
    $\begingroup$ One $1\times\tfrac18$ and two $\tfrac78\times\tfrac12$ rectangles give a somewhat smaller diameter ($\sqrt{65/64}\approx1.008$). $\endgroup$
    – Yoav Kallus
    Feb 22, 2021 at 20:10
  • 2
    $\begingroup$ @MattF. I asked Mathematica for the chromatic number of the graph whose vertices are $\{0,\tfrac18,\tfrac12,\tfrac78,1\}^2$ and two vertices share an edge if their distance is at least $\sqrt{65/64}$. Mathmetica claims the chromatic number is 4, so you seem to be correct in your conjecture. $\endgroup$
    – Yoav Kallus
    Mar 1, 2021 at 17:52
  • 2
    $\begingroup$ @YoavKallus, I can confirm that by hand. For the similar graph whose vertices are $\{0,\frac18,\frac78,1\}\times\{0,\frac12,1\}$, one can enumerate the 18 3-colorings, and find that $(0,y)$ must have the same color as $(\frac18,y)$, and $(1,y)$ must have the same color as $(\frac78,y)$. Thus in any 3-coloring each corner must have the same color as the points on the perimeter at distance $\frac18$ from it. But also in any 3-coloring there must be two consecutive corners of the same color. So in any 3-coloring there must be two points of the same color at distance at least $\sqrt{65/64}$. $\endgroup$
    – user44143
    Mar 2, 2021 at 3:25

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .