4
$\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 degenerate, one can achieve, for each piece a diameter equal 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 necessarily 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

2 Answers 2

Reset to default
2
+50
$\begingroup$

1)) When $C$ is a disk of diameter $1$ and $n$ equals $6$ or $7$, it is easy to show that the minimum maximum piece diameter equals $1/2$. Therefore one of the pieces can be even empty.

Improve this answer
$\endgroup$
4
  • $\begingroup$ Thanks. But as far as I can see, the 6 (or 7) pieces such that the max diameter among them has the minimum value of 1/2 all have the same diameter 1/2, isn't it? So, minimizing the max diameter appears to equalize the diameters - although their widths could be different. $\endgroup$
    – Nandakumar R
    Commented Aug 25 at 14:18
  • $\begingroup$ @NandakumarR No, the pieces diameters can de distinct. For instance, first cut a small regular hexagon $H$ concentric with $C$ and next cut the residual "annulus" into six equal "sectors" (of the diameter $1/2$ each) along the radii of $C$ passing through the vertices of $H$. $\endgroup$
    – Alex Ravsky
    Commented Aug 26 at 3:25
  • $\begingroup$ Thanks for the clarification! The outer 6 pieces cannot have diameter >1/2 but the central hexagon can be shrunk at will without affecting (increasing) the diameters of outer pieces. Marking this question as answered. Hope to have an answer on maximizing the least width among pieces as well. Maybe (just maybe) a much weaker claim holds: "if the max diameter is to be minimized, there exists at least one partition that also equalizes the diameters with that minimum max diameter." $\endgroup$
    – Nandakumar R
    Commented Aug 26 at 3:57
  • $\begingroup$ Another weaker version of the question would be: if maximum diameter is to be minimized among n pieces into which C is cut, what is the upper bound on the number of distinct diameter values - as a function of n? It looks very unlikely that all n pieces can have different diameters. As of now, I can't think of even a C and n where there could be 3 different diameter values. $\endgroup$
    – Nandakumar R
    Commented Aug 26 at 5:42
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
    Commented 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
    Commented Feb 21, 2021 at 22:33
  • 4
    $\begingroup$ One $1\times\tfrac18$ and two $\tfrac78\times\tfrac12$ rectangles give a somewhat smaller diameter ($\sqrt{65/64}\approx1.008$). $\endgroup$
    – Yoav Kallus
    Commented Feb 22, 2021 at 20:10
  • 4
    $\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
    Commented Mar 1, 2021 at 17:52
  • 3
    $\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
    Commented 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 .