TECH-MUSINGS

Thoughts On Algorithms, Geometry etc...

Sunday, December 20, 2020

Partition into Equal Width and Equal Diameter Pieces

 The content of this post is also here:

https://mathoverflow.net/questions/376672/cutting-convex-regions-into-equal-diameter-and-equal-least-width-pieces-2


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.



  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.

0 Comments:

Post a Comment

<< Home