TECH-MUSINGS

Thoughts On Algorithms, Geometry etc...

Friday, February 26, 2021

A Variant of the Borsuk Problem - Least Width

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 (in higher dimensions, hyperplanes) that touch the region.

The following question is a variant of the Borsuk problem which focusses on diameter (https://en.wikipedia.org/wiki/Borsuk%27s_conjecture):

Question: Can every planar convex region with least width = 1 be partitioned into 4 convex pieces such that every piece has least width at least 1/2?

Remarks: If the answer to above is "yes", one can ask the generalization: can every d-dimensional convex region with least width = 1 be cut into 2^d convex pieces such that each piece has least width at lest 1/2? If the answer is "no", one can ask for a better bound on least width.

One can also ask, given a general fraction f, to find that number of pieces such that the least width among them is at least f when any convex body with unit least width is partitioned; and perhaps try to extend the Borsuk problem itself by asking given an f, at least how many pieces are needed so that the diameter of each piece is less than f.

In 2D, we can also look at quantities such as moment of interia about an axis perpendicular to the plane thru center of mass and see how this it can have a bound among convex pieces.

Mathoverflow page: https://mathoverflow.net/questions/384904/a-variant-of-borsuk-problem-based-on-least-width

Sunday, February 14, 2021

Thoughts on Extending the old Fair Partitions Question

Recording some leads from the original fair partition (spicy chicken} question which asks for partitions of ocnvex bodies into convex pieces of same area and perimeter:

1. Are the properties of the space of partitions into n pieces with 3 quantities equal among pieces (rather than 2) well understood (the equalized quantities could be say, area, diameter, perimeter)?

Response from Prof. Roman Karasev: one may first invoke the configuration space of regular convex partitions into $n$ parts, which has dimension $3n-4$. But the number of equations to solve is $3n-3$. Hence there is a problem in dimension counting already. Of course, not all convex partitions are regular and there are in fact more degrees of freedom. But from the point of view of equivariant topology the space of all convex partitions into $n$ parts equivariantly retracts onto the configuration space of dimension $2n$ and then to an $(n-1)$-dimensional poyhedron. This roughly means that equalizing 2 values (one of them is area) is the best possible result attainable with equivariant methods.
------------
2. What are the possible conditions under which the pieces resulting from a partition guaranteed to be congruent? For example, can one have claims like (say):
"if, for 2 values of n (n1 and n2) that are relative prime, a given convex region can be cut into n1 pieces all with 3 properties equal and also into n2 pieces with the same 3 properties equal among pieces (but not into numbers of pieces which are not relatively prime), then, the pieces resulting from both partitions are necessarily congruent"?

The best educated guess for the above quesiton that I heard is that there is no way to guarantee congruence from any finite set of inequalities - iow, there is sufficient perturbative freedom left so that one can cook up a convex region C that allows such partitions into relatively prime numbers of pieces not all congruent but with all the required quantities equal across pieces.
------------
3. Even if only 2 quantities need to be equal among the n convex pieces, if one of them is NOT area, then, things are different. Here is something I just learned from Prof. Karasev:


The current techniques allow to equalize two quantities among pieces when at least one of them behaves like area, that is tends to zero when a part of the partition tends to the empty set (note that this is not the case for perimeter). Moreover, the restriction that the number of parts $n$ is a prime power is also hard to avoid (unless one of the quantities is additive, like the area).

So, there is a chance that say "to equalize perimeter and diameter among 6 (smallest nonprime power) pieces may not be possible"!

Monday, February 08, 2021

Two Centers of Planar Convex Regions

**Definition:** A line segment with both end points on the boundary of a planar convex region $C$ is called a chord of $C$.

1. Consider any point P within a given planar convex region $C$. From among all chords of $C$ that pass thru P, find that chord for which the ratio between the 2 segments into which P divides the chord (longer seg : shorter seg) is a maximum and note this maximum. Now, how does one find the position of P inside $C$ such that this maximum ratio is a *minimum*?

**Remarks:** Numerical experiments indicate that when $C$ is a triangle, the optimal position of P is always the centroid of the triangle. But for general convex $C$, P may not be at the center of mass.

2. Consider any P within a planar convex region $C$. For every angle of orientation measured from P, there is a unique chord of $C$ that passes thru P. Consider the average over the orientation of the length of the corresponding chord. Now, how does one find that position of P such that the average length of chord thru it is *maximum*?

**Remarks:** Numerically, when $C$ is a triangle, the optimal position of P *does not* seem to be on the centroid or incenter of $C$. Note also that the average length of chord thru P can also be considered over each chord starting at each point on the boundary of $C$ and passing thru P - in this case we might have a different optimal P.

Note (additional question): We can also look for that interior point that minimizes the ratio between the max distance from it to the boundary of C and the min distance from it to the boundary of C.

Update(Feb 10th, 2021): Here is the Mathoverflow discussion page on this question. Thanks to Patrick Schnider. https://mathoverflow.net/questions/383415/on-two-centers-of-convex-regions