TECH-MUSINGS

Thoughts On Algorithms, Geometry etc...

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.

0 Comments:

Post a Comment

<< Home