TECH-MUSINGS

Thoughts On Algorithms, Geometry etc...

Wednesday, February 09, 2022

Fair Partitions into non-Congruent pieces

We continue the last post here and the old fair partitions story.

Basic question: Given a planar convex region C and integer n, when is it possible to cut the region into n mutually non-congruent convex pieces such that the pieces all have the same area and same perimeter?

Remarks:
- It is quite easy to cut C into n mutually non-congruent pieces of equal area (just slide a line initially tangent to C perpendicular to itself and chop off a piece when the line has passed over 1/n of the area of C. Then, with the remainder of C, start with a tangent inclined at some other odd angle and repeat). Moreover, even for closed surfaces such as a sphere, such an equal area partition into non-congruent pieces can be done (the last post here, linked above).

- However, it is not immediately clear how to achieve 'fair non-congruent partitions' even for a square. It might well be the case that for any C, there are at least some values of n for which such partitions are NOT possible - indeed, for a disk or for that matter, any centrally symmetric region, such a partition obviously does not exist for n =2; maybe for disk, it is not possible for any n>2.

- A weaker condition on the pieces would be: "not all pieces should be mutually congruent". And apart from the original or basic fair partition question, the condition of the non-congruence of pieces could be added to other variants such as the one where diameter and perimeter ought to be equal among n pieces.

- It is known that for example, a quadrilateral with all angles irrational fractions of pi cannot be cut into n mutually congruent pieces for any n (even if the pieces are allowed to be non-convex) (see this link). So, since fair convex partitions do exist for any C for any n (proved by Avvakumov, Akopyan and Karasev), fair convex partition of such a quad for any n will obviously not have all pieces congruent. Some pairs might be congruent though - at least that cannot be ruled out upfront. Or maybe there are indeed regions for which any fair convex partition into any number of pieces will contain only mutually non-congruent pieces (that would probably take some proving!).

Monday, February 07, 2022

Non-congruent Tiling - 13

Here is Part 12 of this series...

Good News: Dirk Frettloh and Christian Richter have written a preprint where they prove that the Euclidean plane can be dissected into mutually incongruent convex pentagons of the same area and same perimeter. Some further open questions are also stated. So more results are round the corner.

For this post, let me return to a question from part 7:

1. For what values of integer n can the surface of a sphere be partitioned into n convex and mutually non-congruent pieces of same area? (For closed surfaces, convexity could be viewed as geodesic convexity). If such a partition exists for some n, one can ask if one can achieve a fair convex partition - pieces with same area and same perimeter - for some of those n's.

Note: one can replace sphere by general ellipsoids or tori or polyhedra.

Speculation: Even a negative result like: "the spherical surface (or maybe even any ellipsoid or say, toroid) cannot be cut into any number of mutually non-congruent convex pieces or same area (or for that matter, 'same area and same perimeter')" would be interesting!
----------
Update(10th Feb, 2022): Here is a mathoverflow discussion page on the question. It has been shown there by Jukka Kohonen that if only area is to be equalized among n non-congruent pieces into which a spherical surface is to be cut, it can be done - indeed in a vertex to vertex fashion. And it seems achieving fair partition of the surface into n non-congruent pieces would be much harder due to the number of constraints.

Saturday, February 05, 2022

Packing and covering convex regions with congruent convex regions

Some thoughts that proceed from several earlier links, for example:
1. https://mathoverflow.net/questions/407397/least-area-and-least-perimeter-triangles-that-contain-a-convex-planar-region-h
2. https://mathoverflow.net/questions/352563/from-a-given-triangle-to-cut-2-mutually-congruent-convex-pieces-that-together
3. https://mathoverflow.net/questions/357124/on-comparing-planar-convex-regions-of-equal-perimeter-and-area
-------
Given a convex region C and an integer n, we are interested in finding
a. an optimal convex region C_a of maximum area such that n congruent copies of C_a can be put in the interior of C.
b. an optimal convex region C_p of maximum perimeter such that n congruent copies of C_p can be put in the interior of C.
c. an optimal convex region C_w of maximum least width such that n congruent copies of C_w can be put in the interior of C.

Question: Find the shapes of C such that {C_a, C_p, C_w} are pairwise maximally different.

Note 1: Consider C as a pentagon got by joining 2X1 rectangle to a long isosceles triangle of unit base attached to width of the rectangle. The C_w of this pentagon has width 1 and is a unit square. But a quadrilateral with width = 1/2 cut from the pentagon by the angular bisector of the isosceles apex is both its C_p and C_a. I can't think of any C where all C_p, C_a and C_w are wide apart or a C where C_p and C_w are same and C_a is rather different.

Note 2: If we try to find C_d - congruent pieces of maximum diameter - then, the answer could be degenerate.

Note 3: Instead of packing, we can consider **covering ** C with n congruent copies of some convex region such that this covering region has minimum area/perimeter/least width/diameter and compare the various optimal covering units.

Tuesday, February 01, 2022

Max of min and Min of max - 2


Reference: Earlier post

Let us define the distance between two convex regions as the haussdorf distance between them when the 2 regions are kept so as to minimize this hausdorff distance. Consider partitions of a convex region into n convex pieces such that (1) The average of the distance between the nC2 pairs of pieces is minimized or (2) the maximum among the nC2 such distances is minimized.

It seems conceivable (no reasons!) that minimizing the max pair distance need not necessarily make all pair distances equal. This needs some checking...

Will achieving such partitions optimizing the pair distances between pieces have any impact on the area/perimeter/diameter etc. of pieces?

Remark: I learned from Prof. Roman Karasev, that nC2 pair distances is a set of too many quantities to equalize. So, I guess the above thought may not be very useful.