Breaking Pieces from Polygons

Basic Question: Given a unit area 2D region R and a number n, to cut n pieces of a specified type from R so that the maximum fraction of R comes off.

A simple minded greedy algorithm would be to cut the biggest possible piece of the desired type from what is left of R n times.

Case 1: If the pieces ought to be triangles, greedy fails.

Example.

Consider the octagon shown above to be R - it has area 34 units - and let the pieces to be cut be squares and let n = 17.

To the right is shown is the greedy cut. The biggest square that can be cut from the octagon in first step is 5X5 (yellow). Once it is taken off, one is condemned to cut only 0.5X0.5 squares. Cutting 16 of them uses only 4 more units of area from the octagon, thus leaving out an area of 5 units as waste.

To the left is a better cut that begins with a 4X4 square in the middle (yellow)and then 16 1X1 squares can be cut as shown and that wastes only the 4 red triangular pieces with total area only 2 units - this is clearly better than greedy.

Case 2: If the pieces ought to be triangles, again greedy fails.

Example.

Figure above shows a pentagon got by slightly pulling out one of the sides of a square. The biggest triangle that can be cut off from this pentagon is the one bounded by the red lines. If n =2, starting with this biggest triangle broken off obviously gives an inferior result than the  partition achieved by the two black dashed lines.

Case 3: What if n circles are to be cut? I do not yet have a ready counter example for greedy in this case!

Update (Jan4th 2021): 3 actually has quite a neat answer - a counter example. See here: 

https://mathoverflow.net/questions/380035/on-cutting-disks-from-planar-regions

Thanks to J J Green!

Partitioning Convex 2D Regions - Moment of Inertia

 After the original 'fair partition' question of partitioning a 2D convex region C into n convex pieces all of same area and perimeter, one recently worried (http://nandacumar.blogspot.com/2020/12/partition-into-equal-width-and-equal.html) about questions such as whether trying to minimize the max perimeter of n convex pieces would automatically lead to a partition where all pieces have same perimeter.

Then one mentioned instead of perimeter, quantities such as diameter, least width of pieces that could be used as the basis of the convex partition.

Now let me mention one more such quantity which might be of interest - the Moment of Inertia of the pieces with the MI of each piece measured with reference to an axis normal to the plane thru the center of mass of the piece.  One could try to (1) make each convex piece have same moment of inertia  or (2) try to  maximize the minimum (or minimize the maximum) of this quantity among the pieces. 

Another motivation for thinking about so many different quantities - area, perimeter, diameter, least width and now the moment of inertia: Let us restrict our consideration only to polygonal 2D regions. Then, there is a hope that with values specified for a limited set of such global quantities (one might also need to  specify the number of sides n the polygonal region has), one could fully determine a convex polygonal region for any n. By 'limited set', one means a set with number of elements considerably less than O(n).

On Rotating Inscribed Curves

This post is very speculative even by the standards of this blog...

The following are known:

Any curve of constant width (for example, a circle or Reuleaux triangle) can form a rotor within a square, a shape that can perform a complete rotation while staying within the square and at all times touching all four sides of the square (inscribed in the square). IOW, a square can be rotated fully and remains circumscribed about any curve of constant width.

1. In the case of the constant width curve being a circle, its center remains fixed during its rotary motion within the square whereas for other such curves (Reuleaux, say), its center traces a closed curve about the center of the square. When a Reuleaux rotates thus within a square (staying inscribed), it does NOT sweep over the whole of the interior of the square but leaves out small pieces at the corners of the square.

Questions: Are there instances where the inner closed curve C1 is not of constant width and the outer curve C2 is not a square such that this property of C1 staying inscribed in C2 for an entire rotation of C1 can be achieved? A trivial such case is given by any cyclic convex polygon rotating within a circle and staying inscribed. One is looking for something more complex.

Is there any case other than {inner C1 is a circle segment and C2 is a full circle of same radius} where the inner inscribed curve C1, during a full rotation, can sweep over the whole of the interior of the outer C2?

Onto the Minkowski Plane

 From the books by Boltyanski, Yaglom, Gohberg,... one first heard about the Minkowski plane defined with respect to centrally symmetric convex regions. The most basic such plane has a square as the unit circle and the taxicab metric.

General Question: How many of  the questions on partitioning, packing, tiling etc.. pondered on these pages over all these years will go over interestingly onto the Minkowski plane?

Of course, one first needs to understand if at all the concept of area goes over and how. There should be future updates to this post...

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.

2. 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.

Packing with Non-Congruent Regions

Continuing from the question of tiling with mutually non-congruent triangles (and in general, with convex regions) with same area and perimeter, can one think of packing with mutually non-congruent equal area 2D regions all of which form a one parameter family? For example, packing the plane with ellipses, all of same area but different eccentricity.

Can one say something general: (say) such a packing with mutually noncongruent equal area convex  regions belonging to a one parameter family will always be inferior to packing with copies of any one of those regions?

An analogous question can be asked about covering instead of packing.