TECH-MUSINGS

Thoughts On Algorithms, Geometry etc...

Tuesday, March 18, 2025

Stretching Fair Partitions - 2

We add another very speculative claim to those in the last post.

"If a convex planar region C has the property for any positive integer n that at least one convex fair partition of C into n convex pieces has at least 2 (or maybe 3, say) of the pieces mutually congruent, then for any n, C allows a convex fair partition into n pieces that are all mutually congruent - and further, C is either a sector of a disk or parallelogram."

Monday, March 10, 2025

Stretching the Fair Partition question

Can one make claims of the following type?
"If some convex region C allows partition into n convex pieces all of equal area, perimeter and one more quantity, say diameter or least width for all values of n (or infinitely many values of n), then all pieces are necessarily congruent."

If the above is true, one can stretch things a bit and guess: "If all pieces are congruent for all n, C is necessarily a sector of a disk (with the full disk as a limiting case) or a parallelogram (including rectangles). If 'for all n' is relaxed to 'infinitely many values of n', one also has the case of C being a triangle." This latter guess was once posted at mathoverflow.

Note: perimeter and diameter can be nonzero even when a polygon is degenerate but not area or least width. Basically the question/claim is about 3 quantities being equal among pieces (with 2 of the quatities being like perimeter and one like area or vice versa). If 3 quantities being equal isnt enough for the congruence claim to hold, consider 4!

Wednesday, February 19, 2025

Smallest quadrilateral containing a set of points

I am not sure how to find the least area/ least perimeter triangles that contain a set of points on the plane. The guess for both would be that the triangle has an edge coincident with at least one side of the convex hull of points so a plane sweep kind of approach would work.

An apparently more difficult question: How does one find the least area quadrilateral containing a set of points? The quadrilateral is allowed to be non-convex. If the quad is required to be convex, we might be able to manage with a plane sweep type of algo.

Saturday, February 08, 2025

Non-congruent Tilings - 22

Some more tiling questions occured recently. Simply recording them. Hopefully they don't feature in earlier episodes of this series, the most recent being this and this.
-----------
1. Can the plane be tiled by mutually non-congruent triangles all of equal area and with all three edges unique? If possible, one could demand the edge lengths to have an upper bound.
(This question was raised at this earlier episode) and here is another discussion that appears closely related but for the equal area requirement.

2. Can the plane be tiled by mutually non-congruent triangles all of same area and having one angle common?

3. Can the plane be tiled by mutually non-congruent triangles all having two sides common? No equal area constraint here.

4. Can the plane be tiled by mutually non-congruent triangles all with one side and one angle common? No equal area constraint.

And so on...there seems to be no end to possibilities...

Friday, January 10, 2025

Multiple levels of 'hiding' a convex region with copies

This is based on this post at mathoverflow:

The basic question was how to 'hide' a unit cube which is a source of light with opaque copies of itself such that no light reaches infinity. As was not clear to me when the question was raised, this hiding can be attempted at multiple levels. Let us come down to 2D and try to hide a square.

(1) by fixing 4 opaque squares flush with the faces of the light source square. In this case, vertices of the glowing square can emit light that does reaches infinity but what is visible from infinity are only points, no 1-D subset of the square. Here, if one considers the *total outer boundary of the total layout of 5 squares*, the glowing square has a finite intersection with this boundary - the 4 vertices.

(2) as given on this earlier post here (second figure). Here, we hide the glowing yellow squrare with 5 opaque copies (unshaded). In this case, as pointed out by Erich Friedman, rays can possibly squeeze between opaque squares touching each other but unlike (1), the outer boundary of the total layout has no intersection at all with the glowing square. But yes, there can be rays from the glowing square that need only to pass thru just 1 point on the opaque cordon to get to infintiy.

(3) a still more 'secure' cordon with 6 opaque squares given by Prof. Friedman himself in https://mathoverflow.net/questions/468850/how-many-unit-cubes-are-needed-to-hide-a-unit-cube-fully-in-3d . Difference between this and (2) is that any ray from the glowing square has necessarily to pass thru at some interior points of the opaque squares to get to infinity.

IMO, (2) and (3) are both nontrivial with (3) more so. Going to 3D, things can get a lot more interesting.
___
Note: problem 7 of section 2.7 in Research Problems in Discrete Geometry by Moser et al refers to every ray emerging from the glowing body meeting either the interior or boundary of the opaque copies. Here, we have separated the question into 2.
_______
And a different direction: to hide more than one unit square with opaque unit squares - begin with 2!

Saturday, January 04, 2025

On some centers of triangles

This post saves a post deleted from mathoverflow:
-------------------

We try to go further from https://mathoverflow.net/questions/484443/on-3-centers-of-triangles and record more questions.

Given any point P in a triangular region T, we denote by $d_1$, $d_2$ and $d_3$ the perpendicular distances from P to the 3 sides of T. We denote by $D_1$, $D_2$, $D_3$, the distances from P to the vertices of T.

It is known that the position of P that minimizes the Arithmetic Mean of the $D_1$, $D_2$, $D_3$ is the Torricelli point. But I don't know answers to the following:

1. Given any T how does one characterize the location of P within T that minimizes the arithmetic mean of $d_1$, $d_2$ and $d_3$?

2. Which position of P inside T maximizes the Geometric Mean of $d_1$, $d_2$ and $d_3$? Which P maximizes the GM of the D's?

3. Which P maximizes the Harmonic Mean of $d_1$, $d_2$ and $d_3$? Which P maximizes the HM of the D's?

Monday, November 25, 2024

Partitioning a Convex Island into Convex Regions

Background:
1. This paper discusses the problem of partitioning a convex polygon C into n convex pieces such that each piece has equal area and equal length of the boundary of C: basically to divide a convex cake into convex pieces of same area and same amount of icing per piece.

2. Our 'fair partition' (spicy chicken) question (2006), a departure from the above, asks for partition of planar convex region C into n convex pieces all of same area and perimeter. It was proved by Avvakumov, Akopyan and Karasev (https://arxiv.org/abs/1804.03057) that such partitions do exist for all C's and all n.

Now, let us record a variant of the question that lies somewhere between the above two:

Given a convex planar region C to divide it into n equal area convex pieces such that each piece has the same length of cut. Basically, to partition a convex island into n convex parts, with equal length of wall needed by each piece - the coast needs no walls or fortification. And some of the portions could be landlocked - not have any coastline.

Remarks: I gather that the existence proof of the fair partition question (mentioned above) also guarantees the existence of a solution to the new question. Initially, there was some doubt as to the case where C is a convex polygonal region - ie not strictly convex but now, it seems clear that the cut length of each piece in a partition will evolve continuously with the piece itself and that the proof can handle it. So, it appears that this new variant is not really much of an issue. Still, I am keeping this post.