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. Same seems (no rigorous proof) to be the case with maximizing (minimizing) the minimum (maximum) perimeter among n convex pieces.

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.

$\endgroup$
0
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$.

$\endgroup$
6
  • 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 '20 at 7:08
  • 1
    $\begingroup$ Somewhat related: the "three cowboys" problem in Steinhaus, One Hundred Problems in Elementary Mathematics. $\endgroup$ – Gerry Myerson Feb 21 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 at 20:10
  • 1
    $\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 at 17:52
  • 1
    $\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$ – Matt F. Mar 2 at 3:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.