TECH-MUSINGS

Thoughts On Algorithms, Geometry etc...

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.

Sunday, September 22, 2024

Marking out Geodesically convex regions on surfaces of polyhedrons

We refer to any subset S of the surface of any convex solid C as being geodesically convex if for any two points on S, the shortest line on the surface of C that joins them is contained entirely in S - and if there are more than one such shortest path, at least one is entirely contained in S.

Question: Consider any convex 3d solid. We need to mark out its surface into n regions all of equal area such that each region is geodesically convex. First of all one needs to decide if a given convex polyhedron's surface can be so marked out for a specified n - an algorithmic decision question.

It appears that the surfaces of all convex solids of revolution about an axis can be marked out into n such regions for any n.

It seems unlikely that the surface of a regular tetrahedron can be marked out into 5 geodesically convex equal area regions. For even a cube, it is not clear if such a marking out of the surface can be done for any n.

Note: This question was posted at mathoverflow a few days back and simply disappeared!

Monday, August 19, 2024

To rig coins and cubes

Sometime back, I put up a couple of questions at mathoverflow and they got deleted. I believe the questions deserve to survive.

1. Given a fraction α > 1/2, how does one make a coin for which probability of landing heads in a fair toss is α ?

Basically, we need to 'rig' a coin to a specified extent. By coin, we mean a cylinder with low but non-zero height (compared to radius). Obviously, the density should vary within the body of the coin. The radius to height ratio could be chosen suitably so as to achieve the required α . I am not sure what assumptions should be made of the ground on which the coin lands.

2. How does one 'rig a cube' such that the six faces have some specified set of six probabilities on a toss - for example, 5 of the faces could have equal probability but the sixth has a slightly greater probability. This seems a clearer question in that there is no confusion about the dimensions of the object.
------
The questions (espcially the one on coins) had elicited some comments:

- "Fair coins do not really give probability 1/2 for heads. They actually tend to land on the side they started with."
(but as far as I can make out, if one performs the same number of tosses with heads and tails up, this bias could get cancelled).

- "People commonly expect that coin tossing would be mainly affected by the weighting (perhaps just the location of the mass center). Not so; E. T. Jaynes wrote about how the method of tossing is more crucial. He devised three different tossing methods that lead to quite different heads probabilities for the same coin."
(but again, for a fair coin, these biases all seem cancellable by following whatever is the 'complement' of each biased tossing method).

On the whole, my feeling is that for a uniform and equally weighted coin, there are indeed ways of tossing to ensure that as the total number of tosses goes to infinity, the probability of heads does get to 1/2. Then question 1 could be rephrased: how does one alter a coin in such a way that the very manner of tossing that yields 1/2 for heads for a fair coin would yield α probability for heads with this new coin?

Monday, June 10, 2024

An addition to a mathoverflow post

We add to - generalize - this post at mathoverflow and add a couple of questions. The mathoverflow post is on central symmetry. We here talk about any symmetry:

Note: in what follows, instead of "mirror symmetry", one can think of any other symmetry.

1. Which convex solids have the property: all planar sections have mirror symmetry?

2. If a convex solid has the property: all its maximal area planar sections - sections of max area with normal in any specified direction - have mirror symmetry, what can be said about the solid?

Note: in both above questions, we can replace max area planar sections with max perimeter planar sections. One can also consider shadows instead of planar sections; and solids for which both shadows and planar sections have some specified symmetry.

Monday, April 22, 2024

Non-congruent Tilings - 21

Although plenty has been written on this thread, a pretty obvious question seems to have escaped one's attention (at least, looking through all the earlier posts one didn't spot any trace thereof!). Here goes.
The main theorem proved by Kupaavski, Pach and Tardos on the basic question:

Theorem: There is no tiling of the plane with pairwise noncongruent triangles all of the same area and the same perimeter

Question: Can the plane be tiled by triangles all of same area and perimeter that are pair-wise non-congruent except that exactly 2 of them are mutually congruent? Of course, '2' can be generalized to 'finitely many mutually congruent triangles' or 'finitely many pairs of congruent triangles' etc.

This has been put up at mathoverflow: https://mathoverflow.net/questions/469784/trying-to-extend-a-theorem-on-tiling-with-mutually-non-congruent-triangles

Saturday, December 16, 2023

Non-congruent tilings- 20: Rational triangles

The previous episode of this lengthy series is here .

Ref: this mathoverflow discussion .

Broad Question: to tile the plane into rational triangles (all side lengths rational) all mutually non-congruent.

Additional constraints: all triangles should have same area or same perimeter or...

A construction (tiling with mutually non-congruent triangles all of equal area with rationality of side lengths not insisted) presented in detail by Stan Wagon here , it appears, can also be made to yield a tiling of the plane with rational triangles with perimeter unbounded - it appears to give only mutually non-congruent rational triangles, no equality among their areas. A further result obtained by Frettloh (https://arxiv.org/pdf/1603.09132.pdf, more specifically figure 4 therein) indicates that tiling with rational triangles with bounded perimeter also can be got - again with no guarantee on equality of areas.

So, what we could ask for here is for a tiling of the plane into mutually non-congruent rational triangles all with (1)same area or (2) same perimeter or whatever.

An earlier discussion on mathoverflow is here .
--------------
Variant: Rationality of triangles could also be defined as: all angles are irrational fractions of pi. What could one do with them?

Further question: It appears that any polygon with all angles rational can be cut into some finite number of rational angled triangles. Will the question of dividing an n-gon with rational angles into the least number of rational angled triangles have interesting optimization features?

Wednesday, December 06, 2023

A locus problem

This wasn't received well at Mathoverflow. So here goes:
-----------
Given a line segment AB, the locus of points P such that the angle APB has a constant value is a 'biconvex lens' formed by 2 circular arcs that passes through the points A and B. Special case: if APB is a right angle, then the locus of points is the circle with the diameter AB. Ref: https://mathpages.com/home/kmath173/kmath173.htm#:~:text=Loci%20of%20Equi%2Dangular%20Points&text=Given%20a%20line%20segment%20AB,circle%20with%20the%20diameter%20AB.

Question: Given two line segments AB and CD lying on same plane, what is the locus of points P such that the sum of the angles APB and CPD is a constant? What are the qualitative features of this locus and how does this locus depend upon the relative position, length and orientation of the two segments and the value of the angle sum?

Note: Numerical calculations indicate the following: when AB and CD are kept fixed near to each other or intersecting and the angle sum varied, (1) if the angle sum is small, the locus is a connected curve that lies far away from the two line segments and surrounding them and shows concavities; (2) for larger values of angle sum, the locus lies closer to the two segments and appears convex. And in some cases, for still larger values of the angle sum, the locus probably breaks into two closed curves. Basically, we seem to have a one-parameter family of curves that go from convex to non-convexr>

An analogous question in 3D (with 2 line segments - that could be either skew or coplanar - and an angle sum) could give surfaces as loci of P.
Picture below contours of the angle sum measured with respect to a pair of short and intersecting line segments near the origin