TECH-MUSINGS

Thoughts On Algorithms, Geometry etc...

Friday, April 09, 2021

Turning a Containers Question Inside Out

This is a Continuation from http://nandacumar.blogspot.com/2021/03/more-on-oriented-containers-and.html

The paper mentioned on that page solves the problem of finding the smallest area isosceles triangle containing a given general triangle.

Basic Question: Given an isosceles triangle T which is the SMALLEST convex region for which T is the smallest area isosceles container?

Now, in this question, one can replace 'isoceles triangle' with rectangle, ellipse, right triangle etc.. and 'smallest area' with 'smallest perimeter' to generate a bunch of questions.

More generally put, the question becomes (https://mathoverflow.net/questions/389865/on-convex-polygons-contained-in-convex-polygons):
----
Given a convex n-gon C, find the smallest convex region R such that C is the smallest n-gon that contains it.
----
The 2 'smallest's above can independently mean either of 'least area' or 'least perimeter' thus the question is actually 4 questions in one. It seems that for all questions, for any C, R has to touch every side of n along a segment - and thus R should have 2n vertices. Another question which one can ask is if for any C, all or some of the 4 questions have the same R as answer.
Note: If 'smallest' is given other meanings, say 'smallest diameter', there are even more questions in there.

Sunday, April 04, 2021

Similar and non-Congruent Dissections

The following questions have been posted at https://mathoverflow.net/questions/389303/cutting-polygons-into-mutually-similar-and-non-congruent-pieces

1. Is there a non-rectangular polygon P that can be cut into a finite number of scaled down copies of P such that each copy is of a unique size (unique scale factor)?

2. Is there a polygon P that can be cut into a finite number of pieces all of which are mutually similar and of different sizes but are not similar to P?

updates to follow...

Friday, April 02, 2021

Convex Partitions - Max of min and Min of max of Quantities

Reference: This overflow question
This discussion was on partition of convex regions into n convex pieces. The general questions were (1) maximizing the minimum among pieces of some quantity and (2) minimizing the maximum among pieces of some quantity. It is obvious that Area is a quantity which gets automatically equalized among the pieces whether one tries to maximize its minimum value among n pieces or minimize its maximum value among n pieces. However, as noted in above page, it is not clear if the perimeter, diameter etc. have such a property.
--------
Broad Question: How does one classify quantities into these groups: (1) those quantities whose values automatically equalizes among n pieces - into which any given convex region is partitioned - when its max value among pieces is minimized (2) those whose values automatically equalizes among pieces when its min value among pieces is maximized (3) those for which both properties 1 and 2 hold (eg. area) (4) and those for which neither holds in general?
--------
Now, let me record a quantity and a convex partition of a planar convex region where *minimizing the maximum* of that quantity among n pieces NEED NOT lead to the quantity being equal among pieces.

Consider facility location: trying to put n points (stations) on a convex planar region C such that the maximum of distance of a point in C to its closest station is to be minimized.

Covering C with n circles (disks) such that the radius of the largest circle is the least possible seems essentially the same problem. Then, in some cases, in the optimal layout of circles covering C, the circles *need not* all be of the same radius (for example, see https://erich-friedman.github.io/packing/circovtri/ . In the case n =5, the top circle obviously could be smaller than the other circles).

Once we have the layout of circles covering C, we can cut C into n pieces with a Voronoi diagram based on the circle centers - each piece consisting of points for which a particular circle center is the closest station. And since the circles need not be of the same radius, the quantity: "maximum distance to the closest station" which is being minimized across the regions need not be equal among the pieces.

Right now, I don't know any quantity which does not necessarily equalize among n convex pieces when its minimum value among pieces is maximized.

Note: As I learned from Prof. Roman Karasev, "informally, it seems that the natural quantities behave worse in the case when you maximize the minimum, compared to the situation when you minimize the maximum." For example, trying to maximize the minimum value of the *diameter* of n convex pieces will lead to many degenerate pieces.